pathfinding for car racing game in C#

thefire 101 Dec 15, 2006 at 19:20

besides that a car racing game needs AI for opponent cars to find there path, i dont know nothing. i know how to implement the A* algorithm. but how do i use it in my engine. what will be the inputs. obviuosly it depends on the road map. but i dont have one for my designer didnt provide me one. i just have a .X mesh of the city. how to create the map for the city. what will be the format of it. can anybody guide me plz.

10 Replies

Please log in or register to post a reply.

Nils_Pipenbrinck 101 Dec 15, 2006 at 19:55

What we did in our racing games was rather simple.

We started with a closed polyline that defined the ideal line the car should try to follow. Getting your AI to follow this line while not looking goofy is a task on it’s own. You need a good amount of look ahead and make sure the AI can’t steer faster than a human would steer.

The next step was to added some helpers (basically spheres) to the track. We added some userproperties that where used to hint the AI. We used hints like “Use the handbrake in the next curve”, “70mph is the maximum speed here” ect.

Then we added logic to the AI that it was able to recover from crashes, e.g. when driven into a wall, drive a bit backwards, steer towards you ideal line and then switch back into normal driving mode. This is important once a car gets stuck.

The final touch is to add more polylines to the level and add logic that cars detect players and other cars as obstacles. The other lines where used as alternative routes for the AI if they detected that they would run into a crash if they keep driving on the ideal line.

The alternative polylines also give varity to the gameplay and can be used to adjust the difficulty level of the AI. Hint the AI to not use the ideal line for more than 70%, and the enemies will be a bit easier to beat.

Oh yes, before I forget this: To give more varity make sure, that if an AI car is in the first position, let him drive a bit slower (unless you have some kind of slipstream physic *hint, hint, easy to implement*).

That’s basically all. A low tech solution, but with some tweaking and fiddeling of the polylines it gave impressive smart and entertaining enemies.

thefire 101 Dec 16, 2006 at 06:06

i got ur point totally but…
my question again is, how to implement it. as i told u i dont have a map or something for the city. do i have to create or can i work without it. how to draw these polylines. how to manage those hints. A little working example (prefered in C#) will be appreciating.

Reedbeta 167 Dec 16, 2006 at 17:34

Thefire, please realize that people don’t watch this board for your questions every hour, if you don’t get a response just be patient but please don’t re-post in the same thread.

Now, the usual way to apply A* in a complicated environment is to set up waypoints. These are invisible entities located at a point in space, which mark things like intersections, corners, parking spots, etc - basically places that the car can drive to. The waypoints are then connected one to the next by invisible line segments, which form the polylines Nils was talking about. You’ll probably have to place these waypoints manually if your city doesn’t come with any metadata. Alternatively you could try generating them automatically e.g. by going into the mesh, finding all the polygons with a road texture, and placing waypoints on them using some heuristic. Once you have your waypoints and the connections, you can use A* to figure out how to get from one place to another within the waypoint graph, and then let the car drive from one to another along the path found.

Nils_Pipenbrinck 101 Dec 16, 2006 at 17:38

How to get the polylines? Hm. let the artist draw a polyline or polygon shape into the level geometry and mark it with a special name.

If that does not work, add some simple kind of editor into the game. You can draw a top down view of the track and use the mouse to set some control points for the polyline.

You’ll need some kind of debug view like this anyways sooner or later.

I can’t give you any example code. The method I’ve described is rather simple but tied to our race game engine. The AI part is not much more than 2000 lines of code but closely coupled to the physics and game-logic.

Even if I would rip out the guts of it, noone who is not familiar with the details of our race engine would be able to understand anything of it.


thefire 101 Dec 17, 2006 at 12:51

sorry for being impatient.
i think Reedbeta’s theory is very simple and straightforward.
i m using vertices as waypoints. but i dont know how to connect them and get a polyline.since C# does not have a polyline class.
furthermore if i even get a polyline, how am i gonna able to drive on it.
lemme put it to you guys with example

my car is on postion (0,0,0)
i wanna go to (10,0,50) then to (20,0,70) and so on,
i have methods for accelerating,bracking,steering left,right.
if the point is straight ahead, i want to accelerate, if it is not, i have to steer.
its simple enough to say, but i m not able to implement it. C# does not have a polyline class. so right now i m not able to create one.
how am i gonna able to solve this problem. if not code then an algorithm explanation with example will be very nice. thanku

Nils_Pipenbrinck 101 Dec 17, 2006 at 13:35

It seems like you’re looking for a solution where you just need to glue some ready to use classes together. Sorry if I sound rude, but it won’t work that way. You need to learn how to break complex tasks such as AI for a racing game into simple problems. Then you can solve each one individually. Some problems may be solved by using classes from a library, while others are so specialized, that you have to write them on your own.

All in all, it seems like you’re aiming a bit to high for your current skill (otherwise you won’t ask for a polyline class). Start with something more simple, and start to get good in problem solving on your own. You’ll need that skill sooner or later anyways.

thefire 101 Dec 17, 2006 at 14:02

i dont know if it is more than my current skill or not, but i know this that i have to do it. its my university project. i m not that bad in programming, and i’ve got my car physics and collision and my own game engine going fine as well. its just that i m being a little frustrated and wanted to finish quickly since i have to submit my project in some days.thats why i was asking for some examples not for ready to do classes.
yes you are right in terms of A.I. knowledge since i dont know much about this field. if you can’t help me on my terms then you can point out some good articles or tutorials related to the type of A.I. you are talking about. i’ll try to study and implement it (god knows how in this short time).
and tell me if steering behaviour is something better to implement then waypoint solution.

Nils_Pipenbrinck 101 Dec 17, 2006 at 15:40

Don’t look for AI. The computer player part is called AI, but in reality there is no AI going on at all.

What you need to do to get to your waypoint is easy: check on which side of the current drive direction the nearest waypoint in front of the car is:

If it’s on the left, steer left. If it’s on the right, steer right. It’s not rocket science. That stuff is called control theory, and it’s a well researched thing.

If you implement this in it’s most trivial way (like I’ve described above), the car will drive along the chains of waypoints, but will always steer left and right around the ideal line, just like a drunk driver. To get rid of this oscillation effect read up on Proportional plus Integral plus Derivative Controls or in short PID-controls. These will give your car a smooth driving behaviour.

The theory is quite simple, you can read up a good explanation here:

Btw, linking together a physics engine, collision-lib and 3d engine does not count for writing your own engine. If you would have written them yourself, you wouldn’t have asked for a polyline-class. :-)

thefire 101 Dec 17, 2006 at 17:20

thanku. i was implementing the same.
and by the way, i am using my own 3d engine.(linked the physics engine ;-) )
i know i m a newbie. dont remind me every second. and dont worry. just a few months and i’ll be answering your questions in this forum brother :-)
thanku very much for your help nils and reedbeta. you guys are appreciable.

Nils_Pipenbrinck 101 Dec 17, 2006 at 19:41


months and i’ll be answering your questions in this forum brother :-)

That’s the right attitude :yes: