Author Topic: RandTrack : random race-track generator  (Read 16672 times)

andrewj

  • Developer
  • *****
  • Posts: 1357
RandTrack : random race-track generator
« on: July 14, 2014, 11:33:51 PM »
RandTrack is a program which generates random racing tracks for the game The Need For Speed 1 (NFS1), both the original game and the Special Edition.

Web page : http://randtrack.sf.net/

(Rest of this post is the original post, where I was exploring different ways of generating tracks....)




This is not OBLIGE related, but I have been playing around with randomly generating closed-circuit race tracks (just their 2D layout).

The approach used in the following picture is very simple : there are a handful of pre-made shapes, each forms half of the track, and two shapes are randomly picked and connected together, and then sometimes skewed and/or rotated.

I had a few other ideas which did not seem workable:

(a) use the cellular automata logic (used in OBLIGE for caves) to generate a shape and then trace around the that shape to form the track.  Playing with this idea on paper lead to very "blobby" shapes which did not look much like race tracks.

(b) pick a random point and then randomly draw to a new point, etc etc, until we eventually get back to the start, and ensuring that angles are never to sharp or the track never gets too close to itself.  Kinda like how a human would doodle a race track.  This approach would require heaps of back-tracking (restarting) and hence could take a very long time to produce a usable track.

----------

An approach which should be feasable and produce truly random tracks is this: start with a predetermined shape (e.g. circle, but have several) which consists of number of short line segments, maybe 100.  Then "iterate" to produce a new track by deformation, moving each vertex by a small random amount, while maintaining angle limits and ensuring vertices don't get too close to the track.  Keep iterating for so long, e.g. 500 times.  Would probably need to test the result is OK (e.g. not returned to a boring circle).  You could also create some features at the beginning (straights, chicanes, hairpins) and maintain those features during the iteration process.
« Last Edit: August 26, 2014, 05:21:24 AM by andrewj »

Glaice

  • Contributor
  • *****
  • Posts: 1108
  • Veteran OBLIGE modder
    • The Doom Video Vault
Re: Random race-track generation
« Reply #1 on: July 15, 2014, 07:25:50 AM »
Looks like an interesting change of pace instead of being focused on Oblige the entire time :)

De-M-oN

  • Posts: 126
Re: Random race-track generation
« Reply #2 on: July 15, 2014, 02:39:45 PM »


I've sent you mailanswer btw ;)

For NFS1: If you got it working - Now you only need to add support for slopes and twisted turns. So much more it isnt anymore with NFS. You dont need to consider ai speeds since there is no possibility to edit that so far (I think it is hardcoded) and you dont need to consider lighting (NFS1 has no lighting), slope steepness doesnt matter as well for physics - car can go up even a straight up 90° angle street in front of you rofl. So basically its really the track shape alone. Would be awesome if you manage a way doing this :) The pictures look promising so far :)

So yes - look into the game and you'll see its not that much you have to consider.

And there are not only circuits in NFS1, there are also segmented point a to point b tracks - means this type of tracks dont need to be a closed circuit. The program should offer which track you want to modify, since you cant add tracks to the game, just modify existing ones.

For NFS 4 high stakes there is more known about the formats and for it exists the T3ED editor which is further developed by an other person and allows even to modify ai speeds and such and you would need to consider physics (not too steep slopes which the car cant go up for example^^ steep slopes are cool, but must be considered that if its extremely uphill that the car can do that hill :D)
For this game would be awesome as well, but I dont know how much more work it would be for you to support nfs 4 too (but definitely would much more to consider). But thats only dreaming and brainstorming :P
(meh I edited this one so much now in the hope you dont understand me wrong. I know it is already enough work for you to get nfs1 in :) )

I'm totally happy already to see even this thread.

Thank you so much

PS: I want to drive the track shape of picture 3  ;D ;D

oh damn if you get this working - This would be so goddamn awesome

Quote
This approach would require heaps of back-tracking (restarting) and hence could take a very long time to produce a usable track.

Time doesnt matter. Even if it would take an hour to create one track wouldnt bother me. I mean that serious.
You do great work.
« Last Edit: July 15, 2014, 06:08:30 PM by De-M-oN »

flyingdeath

  • Posts: 212
Re: Random race-track generation
« Reply #3 on: July 16, 2014, 08:49:39 AM »
First, sorry for lack of feedback on last version of oblige, but you gave me very little to complain about so... Will have feedback soon.


But this sounds like a cool project. First before I forget, TORCS is an open source racing "game" that was made, if I am correct, for "racing AI" competitions. The track layout files are very simple and can be edited in a text editor, though the actual track model is separate, and I know less about that, as there is a program for converting the track layout into a model. The advantage of this program is that the AI's can race custom tracks without any fiddling about, and are very tough to beat. It is however punishingly unforgiving to race even with an analogue joypad, but maybe take a look.

If you are making track for nfs1, then the layout does not have to be a circuit. The reason I bring this up is because I have an idea for how I might go about generating a track, but it will not produce a circuit.

First you need information about the acceleration of some benchmark vehicle. You also need a function that converts the current speed of the vehicle into a turning circle. Then you simulate the vehicle accelerating across an empty field, and draw the track to follow the vehicles path. When the program decides to put a bend in, it looks at vehicle turning circle, and if it's an easy corner, it will be less than the tuning circle, hard will be more, though the funnest corners will be very near to the vehicles turning circle (I reckon). If the corner is sharper than the turning circle of the car, the simulated cars speed is reduced to a value where its turning circle matches the steepness of the turn.
To really make this work there needs to be some calculation involving the width of the track, as even a sharp turn on a very wide track will be easy to tackle at high speed, unless the corner is very long. Also you would need something to stop the track overlapping. Also hills and road camber will have massive effects on the speed at which you can take a piece of track, and you must avoid putting corners after jumps!

The deformation idea sounds pretty cool, and you could try lots of different types of deformation, find an article on deformation, or types of symmetry, and go wild.

Also really abstract, recursive, fractal type things might be cool to play with. The dragon curve with a low (30-40 degrees) folding angle looks like a particularly tricky track, or maybe you fancy a lap around Gosper island.

You could also produce tracks by adding lots waves together with different amplitudes and wavelengths (and phase), converted into angles for the track to change by, or forming the waves into a ring, and make sure all the wavelengths are factors of the ring length. (This is basically additive synthesis)
« Last Edit: July 16, 2014, 09:12:04 AM by flyingdeath »

De-M-oN

  • Posts: 126
Re: Random race-track generation
« Reply #4 on: July 16, 2014, 05:26:50 PM »
Quote
Also you would need something to stop the track overlapping

That is very important. Even NFS 4 High Stakes doesnt support overlapping.

Quote
and you must avoid putting corners after jumps!
No he doesnt have to. Just a lessened chance that this happens* - can be raised up probability if you choose in the program a higher difficulty (yes course difficulty as an option would be good. So if you choose "easy" for example you would get an easier/fast track. And a mixed up (or random whatever you want to call it) possibility.

*= Because you just would have to brake before the jump. No problem. Even some original tracks of nfs series have a corner behind a jump. Remember for example NFS 2's Mystic Peaks after the bridge - ok the corner is not the sharpest, but sharp enough having to brake before the jump if one of the faster cars. I dont remember at the moment a better example. But anyway - this isnt a problem, its just braking enough before the jump. It just shouldnt be the case for every jump, so a lessened probability for happening this is enough.

The AI has not much priority to me and should be even impossible for nfs1 to consider. No editor available to change them, so I assume they're pretty hardcoded. But doesnt matter me. A randomized track shape is totally enough to me.

I'm so happy that you try to do this. Thank you again so much :)

andrewj

  • Developer
  • *****
  • Posts: 1357
Re: Random race-track generation
« Reply #5 on: July 17, 2014, 04:08:04 AM »
Interesting thoughts flyingdeath, and please no need to apologize, this is only a hobby after all.

Oblige 6.10 did implemented your idea of moving some final battles of a map into an earlier (bigger) room, though it happens fairly rarely because the final room often has a locked door.

back on topic, I think my deformation idea is probably what I will end up using, since it is able to make open tracks too (just start with an unconnected shape), probably need more segments but also require less iterations.

Big disadvantage of deformation method is not supporting cross-overs easily.  Sounds like NFS does not support them anyway, but other games do.  Something I will not worry about yet.

For slopes along the track, I am planning to create a random heightfield (fractal mountain) and the road will be planted on top of it (or can be dug down a bit).  This also decides whether the sides of the track are high or low.

The twisting (camber?) of the track I'm not too sure about, will probably try having the heightfield provide a small portion but the main portion being the curvature of the track -- and here some of the car physics and expected speeds would come into play.

De-M-oN

  • Posts: 126
Re: Random race-track generation
« Reply #6 on: July 17, 2014, 12:51:45 PM »
Quote
Sounds like NFS does not support them anyway

The cause for this is fairly similar to doom. You have a 2D track shape - like doom its 2D level architecture as well has. Height differences are stored as coordinate position and value like doom with its info at sectors and value. overlapping the shape would lead to invisible wall or even you drive out of the track or at worst case the game crashes entirely.

For curcuit courses it is very important that the start and finish is closed accurate. If the finish line overlaps some pixel the start of the track it works if not too much - but chances are there that the game doesnt register the lap and stays at lap 1. But better would be if its pixel accurate closed - if possible - was not always that easy via the track editor to do. A program which generates the course instead of moving the shape via own hand will sure work better :D And even more important is, that there is no height difference between start and finish.

Quote
The twisting (camber?) of the track I'm not too sure about, will probably try having the heightfield provide a small portion but the main portion being the curvature of the track -- and here some of the car physics and expected speeds would come into play.

twisting means you lift up only one side of the track.

Here a screen of a twist to left direction:

http://abload.de/img/dosbox_2014_07_17_21_xbiek.png

If they're too steep you fall into the road and drive it straight again (hard to explain via text and english as a german :D ). This needs a steepness limit so that this doesnt happen.

leileilol

  • Posts: 6312
  • Posts: 78
  • Posts: 84
    • my sirt
Re: Random race-track generation
« Reply #7 on: July 17, 2014, 07:47:56 PM »
Seen the Z Kart project?

Could be another vaporware as far as all those past ambitious kart projects are concerned though
Project Leader of etc., a free first person shooter based on etc. licensed under the etc. license

andrewj

  • Developer
  • *****
  • Posts: 1357
Re: Random race-track generation
« Reply #8 on: July 18, 2014, 05:25:54 AM »
Yeah I can see how the "twisted" road needs to curve from one side to the other (I was probably thinking more in planar terms).  But curving side to side should not be difficult to do.

I think the NFS engine might be able to handle a closed circuit which crossed itself -- to me looks the rendering is very much done "along the track" rather than in real 3D terms, and the cars and objects seem to be relative to the virtual road.  Might be interesting to try it and see if it works.

@lei: never heard of Z Kart, searching finds a guy who made his own electric car and a Dragon Ball game.

leileilol

  • Posts: 6312
  • Posts: 78
  • Posts: 84
    • my sirt
Re: Random race-track generation
« Reply #9 on: July 18, 2014, 03:58:35 PM »
Project Leader of etc., a free first person shooter based on etc. licensed under the etc. license

andrewj

  • Developer
  • *****
  • Posts: 1357
Re: Random race-track generation
« Reply #10 on: July 19, 2014, 02:32:51 AM »
Heh ok, kart racing in ZDoom.

andrewj

  • Developer
  • *****
  • Posts: 1357
Re: Random race-track generation
« Reply #11 on: July 23, 2014, 02:13:01 AM »
Before I can generate the tracks, I need to fully understand the format of the tracks (the TRI files).

The nfsspecs.txt is very helpful, but it is incomplete, and lacks information about SE (Special Edition).

To help understand the track format, I am working on a program which can load the tracks and draw what the tracks look like, show where objects are, etc....

Very early screenshot, so far it can only draw the "virtual road".  Later I will make it show the objects (so I can figure out the correct scaling of the deltas), and after that will draw the "actual road" (what is rendered in game).  Also need to be able to load the FAM files which contain the textures and sprites, and ability to draw the road in 3D .  These things will take a lot of time!

De-M-oN

  • Posts: 126
Re: Random race-track generation
« Reply #12 on: July 24, 2014, 05:42:20 AM »
http://www.share-online.biz/dl/KB00V79NOVH

This file may help you.

This comes with the Track editor. Open it with a texteditor (notepad)

Info about NFS SE will be hard I think. But the converter I linked you in email should help out? So it could create tracks for NFS and the converter could convert it to NFSSE format.
But we would need to test if it does the conversion reliable.
_
ow even the objects? my request was only to have random generated track shapes. Even drawing the road in 3D? wow..
You do much more work than I requested. Thank you so much so far! :-* :) :)

andrewj

  • Developer
  • *****
  • Posts: 1357
Re: Random race-track generation
« Reply #13 on: July 25, 2014, 05:09:35 AM »
3D rendering is probably not needed after all, and TRACKED can show the textures and objects in a FAM file, so doing it myself is not really necessary.

Thanks for the NFSTEU.BAS file, looking at it briefly now, I don't think it has any extra information about the track format in it, but I will double check.

For my program, called RandTrack, it will create tracks for the Special Edition.  Maybe in the future I will make it support plain NFS1.

My first planned task is to generate closed tracks which replace the TR1, TR2 and TR3 tracks.  When that is working well (it may take a long time), then support other TR tracks, and after that support the AL,CL,CY tracks and open tracks.

andrewj

  • Developer
  • *****
  • Posts: 1357
Re: Random race-track generation
« Reply #14 on: July 29, 2014, 05:26:54 AM »
De-M-oN, could you please test the track in the attached zip below.

The track replaces TR2.TRI and is for the Special Edition. It is a very simple track, but it is a good start I think ;)