Jump to content
  • Advertisement
Sign in to follow this  
Alistair_Hutton

AI for Vector Racer - is A* what I want and if so what heuristic?

This topic is 3591 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm writing a version of that boring-lecture classic Vector Racer (if you don't know what I mean have a look here: http://vectorracer.boschloo.net/ I have the game working for hot-seat multi-player but I'm looking to add AI bots for humans to race against. I'm looking for the bots to be able to move round the track without augmenting the track with any AI-only information. In my version of the game there is no penalty for moving onto the same space as a another player and you're immediately eliminated if you cross a wall (or there's another mode where your car is halted, vector reset to 0 and you suffer a turn penalty instead). Anyway, I thought that this would be a simple case of coming up with a heuristic for A* but I find myself stumped, I simply can't come up with an admissible heuristic, nor can I work out how to get the search to search for an entire path round the track. I suppose if I think of distance to checkpoints rather than number of turns taken that might get me something workable. So is A* the right approach to take here and if so anyone have any idea about a heuristic to use?

Share this post


Link to post
Share on other sites
Advertisement
A* would definitely work. Remember that the current velocity is also part of the description of the node.

A constant 0 is always an admissible heuristic, in which case A* degenerates into breath-first search. I'm sure you can do better than that, but if you can't think of anything you can finish the rest of the program for now.

Share this post


Link to post
Share on other sites
So it turns out A* is a good fit as I can't come up with a decent heuristic involving turns taken.

However, greedy search using combined distance to all checkpoints not yet passed works a treat. Yet again I should have started with the simplest solution and increased the complexity rather than yelling 'Eureka!' when I hadn't fully grasped the problem.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!