Finding Paths through starfields

I am new to AI stuff, however, I have an AI type problem.



You know in eve-online how you can click on a star and it will plot a course to that star from your current star, through other stars



Now, I have a galaxy of star locations, and the limiter is distance between stars (lets say for this example you can only warp 5 units)



so how can i build a path of warping between stars to a desired location quickly and on-the-fly as in eve-online?



a brute force method would simply be too much… so this has been baffling my mind for some time now



Thanks for any help.


AStar (A*) is probably the key word you need.

Well, since EVE online has jump gates that can only be linked to certain systems, I think something like a node graph would also be helpful. You’ll have to forgive me if ‘node graph’ is not the right term. It has been some time since I’ve looked into it.



Also, for A*, this could come in handy.

http://www.gamedev.net/reference/articles/article2003.asp

AStar is exactly for that, finding the best path along a set of nodes with interconnections that have different costs.

normen said:

AStar is exactly for that, finding the best path along a set of nodes with interconnections that have different costs.

Oh right, I was thinking it was for a grid always. I need to start reading more into these things, forgetting happens way too easy.