pathfinding for car racing game in C#
Posted 15 December 2006 - 07:20 PM
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 city.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.
Posted 15 December 2006 - 07:55 PM
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.
Posted 16 December 2006 - 06:06 AM
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 it.how? 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.
Posted 16 December 2006 - 05:34 PM
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.
Posted 16 December 2006 - 05:38 PM
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.
Posted 17 December 2006 - 12:51 PM
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
Posted 17 December 2006 - 01:35 PM
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.
Posted 17 December 2006 - 02:02 PM
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.
Posted 17 December 2006 - 03:40 PM
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: http://www.peci.org/...rview1_1002.pdf
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. :-)
Posted 17 December 2006 - 05:20 PM
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.
Posted 17 December 2006 - 07:41 PM
That's the right attitude :yes:
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users