Algorithm for car racing game

Restore Saved Population Restore a previously saved population. Suprise Toggles drawing, makes the simulation faster. New Population Keeps the generated track and restarts the whole car population.

Create new world with seed The same seed always creates the same track, so you can agree on a seed with your friends and compete. Mutation size The range each gene can mutate into. Lower numbers mean the gene will have values closer to the original. Elite clones The top n cars that will be copied over to the next generation. View top replay Pause the current simulation and show the top performing car. Click a second time to resume simulation. Then, relative to the current position of the car, the perpen- and the rear wheels.

The lateral force is formed in the oppo- dicular segments connecting the right and left boundaries of site direction to the lateral velocity of the vehicle. The center the track are identified. This process is repeated for each me- of the circle is found using the current position of the car, the ter of the visible section of the track, thus, constructing a seg- radius and the direction of the lateral forces. When the car is ment per a meter. Using the information of the current dis- on a straight line this radius is infinite.

These lateral forces are depen- the existing track model. For smaller angles the Additionally, the track is annotated with the bend infor- force has a linear correlation with the slip angle hence can be mation. The curvature is cal- ness. Slip angles are calculated based on the lateral and lon- culated by aggregating the heading changes of consecutive gitudinal velocities of the car Vlat , Vlong , the distances from track segments. This bend information is useful in determin- the front b and the rear c axles to the center of gravity of ing the optimal acceleration on a turn.

Fitness for the considered trajectory is incremented for each This actual trajectory is defined with the lateral and longitu- track segment that intersects with the trajectory as shown in dinal velocities of the car, the angular motion, the size and Figure 2.

For each of these intersecting track segments, the the mass of the car and the steering angle. For the consid- ered simulation platform, the mass and the dimensions of 1 Note that the particular sensor distribution can be a prop- car are not available. Therefore, we use initial assumptions erty of the physical car or the simulation environment in case and utilize a low pass filtering technique to update the map- of gaming.

For example, in the SCR default setting these sen- ping function of the centripetal force, for a given slip angle. Then the specific mutation operator for the gene is applied. We have considered two standard mutation strategies relevant to our problem representation and the best is selected subsequently. We have also studied another alternative a nonuniform mu- Algorithm 2 fitness function tation with a fixed distribution. This mutation changes the for each visible track segment s do current value slightly by adding a small variable drawn from if trajectory intersects s at p inside the track then a Gaussian distribution.

As shown in Algo- 4. As stated in the latter part of the Algorithm 2 we consider the trajectory based fitness for the acceleration also. First we calculate the distance to the intersection point where the cur- rent trajectory collides with one of the left or right bound- aries of the track possibly in a bend. Let us call this safe distance. This can be approximated using physics formulas Figure 3: car rectangle in blue trajectory long line in red on linear motion.

Similarly, the stop distance, within which intersection with obstacles circles in colors the car can be stopped if brake is applied to the current car The opponents in front are considered as obstacles with status, is calculated. If the safe distance is larger than the pos- which intersection would reduce the fitness of a trajectory. In this case fitness is incremented based jectories that intersect with the obstacles.

For each intersect- on the calculated speed at the safe distance i. In contrast tance from the car to the collision point as shown in Algo- to this scenario, if we are already too fast and close to the rithm 3.

For static obstacles when they are intersecting with track boundary possible collision , we prefer to brake and, the car trajectory closer to the current position of the car, fit- hence, fitness is decremented based on the speed at the colli- ness is reduced for that trajectory more.

For example, as sion point the higher the speed, the larger the fitness decre- shown in Figure 3 the obstacle that intersects with the tra- ment. As explained in the beginning of the Hence, only if the opponent velocity is less than ours it is section 3, each individual consists of two different genes with considered as a potential obstacle, otherwise it will not be varying data ranges.

Therefore, we define two variations of colliding anyway. For stuck man- The basic approach on fitness evaluation for acceleration agement we use a simple fitness strategy. Here, the gear is discussed in section 3 is safe although it is not very efficient. The fitness is evaluated based on how Therefore, we introduce a slight adjustment to the fitness much the car position is close to the track center and the car evaluation criteria for acceleration to increase the considered heads straight front.

The design of this EA is similar to the safe distance further where the actual distance is large or de- basic EA used for regular driving except for this fitness crite- crease it further where the actual distance is already small. This adjustment can mitigate any error due to track model building.

We use two linear functions to adjust the safe dis- 4. This adjustment changes the safe distance cle controller design to our evolutionary driver where appro- used in the original fitness function in Algorithm 2. Then priate. The auto gear system is an example, that we can use the last two lines of the basic fitness function is replaced by the popular mapping on optimal gearing based on engine the Algorithm 6 rpm [4].

For traction control also we use a few standard rules used in car physics [4, 15]. Similarly we apply ABS on top of Algorithm 4 angle based adjustment factor the already chosen brake value from the optimizer.

Note that a dynamic change does not cause re-optimization but only a reevaluation of the cur- rent individual immediately after the change. A typical run Algorithm 6 fitness adjustment for efficient turning of the algorithm is observed to be effective. We be- 4. Nevertheless, we have taken the visible area of the track only. For that, nario it is not covered in the basic EA used for driving. Alter- we have chosen 3 other best competitors of SCR champi- natively, we incorporate stuck management into our evolu- onship [10] Autopia [14] the all time winner, Mr Racer [18] tionary optimization model through another EA to optimize the winner of SCR championship at GECCO and the actuators on stuck situations.

We have stuck situation is observed it is awakened and the program analyzed the behavior of these drivers for several groups of control switches from the regular optimization process driv- tracks oval, road and dirt provided by the TORCS simulator ing EA to this specialized EA.

Once again, when the car is and also for a set of random tracks generated using the track in safe position, this EA goes back to sleep mode saving its generator by Cardamone et al. The size and the physi- current stuck recovery controller values in its current parent cal factors of the tracks in the first three classes have major individual. Then the regular EA runs and once again may differences. Then the stuck EA We have evaluated our controller based on an established resumes the optimization process from this saved individual.

This competition set up consists of 3 stages the warm-up, EVOR was catching up closely and the other competitors the individual race and the final race. Similar to the com- stayed reasonably behind. EVOR currently addresses the petition, for our experiments also game ticks are pro- slipperiness of the tracks well with its traction control.

We vided for the warm up session. During this stage drivers can believe that by incorporating bump detection feature to EVOR, build track models or tune any parameters. Then the cars we can improve its performance on dirt tracks further. This time is approx- imately equal to seconds as a game tick is around 20ms.

The starting positions of the competitors are deter- dom track generator presented in Cardemone et al. These mined according to the results of the individual race stage. Running on several laps means the experiment is repeated Results show that EVOR has traveled the longest distance for several times, thus guarantees the fairness of the results for the half of the random tracks see Figure 4.

Experiments were conducted in a Ubuntu Linux In the default also. For each track all the competitors were set to race to- mode the damage, the lap-time and the fuel limits are en- gether for 10 laps.

The starting grid was based on the per- abled. The results are shown in Table 1. The end results are quite similar to the previous ex- 5. The shapes and slopes are the winners of the race with opponents too. However, slightly differ in the oval tracks provided with the TORCS there are some interesting scenarios due to opponents ob- simulator. Road friction, aerodynamic and other physical ef- served during these experiments. Due to the strengths of fects are quite similar in all oval tracks.

The results of the opponent handing and stability EVOR could win three ad- four drivers raced individually on the oval tracks are shown ditional races in the final round than the previous individual in Figure 4. These results show that for 4 out of 5 oval tracks race round.

These were on tracks forza and wheel-2 previously EVOR has bridged the largest distance within the given time won by Mr. Racer and torcello-mountain-snow won by Autopia budget of game ticks. These effects are depicted in tory optimization has provided the better path and the speed the results shown in Figure 4 and Table 1. Although, EVOR for these tracks than other drivers. ICER with good bump detection ca- 5. They with high damage rate in this high bumpy road thus could are significantly different to each other with regard to many not complete the race.

This was not observed in the individ- aspects unlike oval or dirt tracks that share similar condi- ual race round as its only held for ticks within which tions within the group. The selected set of road tracks repre- most of the drivers could stay in the TORCS damage limit of sent all different sub groups within the road group provided The road tracks can be of various the opponents round that is even better than the 17 out of 30 shapes, widths, as well as of road friction.

Actually, you could even combine them, and use a genetic algo. Honestly though, brute force would probably work fine on a constrained track, since you can toss out a subtree if you crash and crashes are common for bad paths. Edit : Those path finding algorithms only work if you don't have additional rules and conditions.

For example if you also have velocity and centripetal forces you're out of luck. If you don't have those advanced conditions you're better off with a simple path finding algorithm as stated in other answers. Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Collectives on Stack Overflow. Learn more.

Asked 10 years, 6 months ago. Active 10 years, 6 months ago. Viewed 7k times. Improve this question. Mat Mat 8 8 silver badges 24 24 bronze badges. Presumably the answer would be to construct some sort of racing line, then look two or three steps ahead to evaluate speed and position versus the racing line? Or is that just restating the question? I can think of some ad hoc methods of constructing a racing line from first principles, but I suspect a proper algorithm would be a smarter move.

One way to get great answers would be to organize a challenge on the code golf stack exchange website. Define a standard way to represent the tracks and answers, and award a bounty to the best solution.

I think it would be a lot of fun! Jarrod: Vector Racer Online only lets you use pre-defined tracks probably a lot of pre-computation has gone into them , and from what I can tell it doesn't give you any code.

Add a comment. Active Oldest Votes. How it works Because each move costs exactly 1, it's possible to use a breadth first search through the 4D state space to find an optimal solution.

Examples stopwatch racetrack 30 3 90 10 Starting at 30, 3. Goal is 90, No obstacle. Elapsed time: ms stopwatch: Process completed with exit code 0. A circular obstacle of radius 25 is centred at 50, Improve this answer. I'll get through your code tonight to see whether I understand it and whether it serves my purposes.

Mat BFS may fail with larger, more complicated tracks since it requires an exponential amount of memory. Aaron, my BFS needs memory at most linear in the size of the state space. This bounds the memory for storing the traceback path for any state, and it also bounds the size of the queue, since we only ever add a state to the queue if it has not been seen yet. BFS is exponential in the solution depth, but for this problem the solution depth is constrained by the size of the grid.

The effective branching factor is also low it seems somewhat high, until you consider all the states that are cut off by the boundaries. Aaron, sorry to go on, but "BFS is exponential in the solution depth" is only true when the number of distinct states that can be reached in n steps is exponential in n, which frequently is not the case.