Home Forums Programming Pathfinding Algorithms

Welcome to our forums. These forums were active from 2003-2014. We have now decided to close them down, but will leave them here as an archive.

Remember you can send us feedback, news, jobs and content ideas by clicking here.

If you're really stuck for time, email news@gamedevelopers.ie.

You can also follow us on Twitter @gamedev_ie 

 

 

This topic contains 16 replies, has 7 voices, and was last updated by  philippe_j 12 years, 1 month ago.

  • Author
    Posts
  • #4687

    darf_danno
    Participant

    Not sure if this is the correct topic for this but what the hell. :roll:

    I am currently researching pathfinding algorithms and am totally drowned in A* stuff.
    I am looking for algorithms that may have been used in games before A* became pretty much the standard. I have some text’s on obstacle avoidance, and basic pathfinding using waypoints.
    Could anyone give me a prod in the right direction. Doesnt matter if the algorithm was rubbish or not, or includes code or not (at the moment I would not like to see any code, that will scare me :shock:), I would still like to know about it.
    Thankies :D

  • #26409

    erckle
    Participant

    hey,
    if you can, check out Russell and Norvigs book – Artificial Intelligence: A Modern Approach (2nd ed). It has a whole section dedicated to the area of Searching (Chapters 3-6). It covers everything like breadth-first, depth-first, iterative deepening, Greedy, A*, Hill Climbing, etc etc.
    The URL to the accompanying website is:

    http://aima.cs.berkeley.edu/

    Also, Mat Buckland has a book called programming game ai by example, which is definately worth the read if your into game ai.

    Also try gamedev.net article section on ai:
    http://www.gamedev.net/reference/list.asp?categoryid=18

    if that doesnt help you out, I guess just try googling the techniques Ive mentioned above

  • #26410

    Skyclad
    Participant

    Aye, that first book is a tough read, but a solid introduction.

    As always, Wikipedia is god – http://en.wikipedia.org/wiki/Search_algorithm

    At the end of the day, A* is the way to go though.

  • #26411

    peter_b
    Participant

    Not sure if this is the correct topic for this but what the hell. :roll:

    I am currently researching pathfinding algorithms and am totally drowned in A* stuff.
    I am looking for algorithms that may have been used in games before A* became pretty much the standard. I have some text’s on obstacle avoidance, and basic pathfinding using waypoints.
    Could anyone give me a prod in the right direction. Doesnt matter if the algorithm was rubbish or not, or includes code or not (at the moment I would not like to see any code, that will scare me :shock:), I would still like to know about it.
    Thankies :D[/quote:3332dc5f9c]

    ive got some stuff in my thesis.
    check it out, i also did some stuff on new approaches to path finding.
    up til a* mostly hacking and dijkstra were used.

    http://student.cs.ucc.ie/~pb2

  • #26415

    erckle
    Participant

    you could also check out the essays and tutorial sections of
    http://ai-depot.com/
    Theres some good stuff there, including a tutorial entitled – Beginners Guide to Pathfinding (found here: http://ai-depot.com/Tutorial/PathFinding.html)

  • #26446

    kyotokid
    Keymaster

    This newsletter may be worth subscribing to? :

    http://five.pairlist.net/pipermail/gameai_news/2005/000002.html

  • #26452

    philippe_j
    Participant

    peter_b : correct me if I am wrong, I am a bit rusty here, but Dijktra is just an earlier version of A*, anyway.

    darf_danno :
    just think about PacMan, the path finding algorithm is pretty basic, there, and yet it’s a classic that has been used many times elsewhere, before A* became cheap enough (computationally speaking) to be used.
    Essentially, the ghosts lookup PacMan’s (x,y) position, and try to get closer to that… if a wall is blocking them, well, they try to slide along, if they can’t they just get stuck. Note that this ends up being a part of the gameplay, so it doesn’t really matter that it’s a bad pathfinding algorithm…

    Most of the path finding going on now is just trying to adapt the concept of A* to whatever the game environment is.
    The AAS system used in Quake III, for instance, is just that. The difficulty is not finding a path anymore, it’s creating the nodes that the algorithm is being used on, in an efficient manner.
    Do you tile your 3D space in thousands of little cubes that act as nodes ? Or do you decompose the environment in rooms, which then become the nodes, but how do you do if it’s an outdoor enviroment, etc, etc.
    Once you understand it’s not the algorithm you have to look at, it becomes very interesting indeed. IMHO :)

  • #26595

    hugh
    Participant

    peter_b : correct me if I am wrong, I am a bit rusty here, but Dijktra is just an earlier version of A*, anyway.
    [/quote:5ec0ae7df4]

    This is roughly speaking correct. Dijkstra’s algorithm is designed to find the shortest path between two nodes on a graph where there are weights attached to the edges. These weights might represent distances between the nodes. It achieves this by basically carrying out a form of optimised exhaustive search which means it checks all possibilities in a breadth first manner.

    A* however adds a heuristic that guides it in the direction of trying what it estimates to be the most promising direction through the graph first. This is often called best-first search. If the estimate it uses is a good one then it will find the shortest path quicker. If it’s a bad one then it won’t, and probably perform worse than Dijkstra. In the case of pathfinding in games, this estimate can be simply linear distance, and unless you have a mad-looking graph with lots of nodes down dead-end corridors and so on, then this forms a good estimate and it works really well. Russel and Norvigs book mentioned already would cover this stuff. There’s also one by Luger and Stubblefield which is good too.

    The Dijkstra algorithm was developed by Edgar Dijktra who was this Dutch computer scientist who died a few years back. Dijkstra literally wrote the book on more or less everything to do with algorithms in computer science. When he was writing this book, he decided the existing tools for typesetting mathematical formulae weren’t good enough, so he went and developed the whole Tex system to do it with. Imagine deciding to write a book and starting off by building your own word processor to do it with ……..

    Wow that was pretty nerdy of me to mention that.

    Most of the path finding going on now is just trying to adapt the concept of A* to whatever the game environment is.
    The AAS system used in Quake III, for instance, is just that. The difficulty is not finding a path anymore, it’s creating the nodes that the algorithm is being used on, in an efficient manner.
    Do you tile your 3D space in thousands of little cubes that act as nodes ? Or do you decompose the environment in rooms, which then become the nodes, but how do you do if it’s an outdoor enviroment, etc, etc.
    Once you understand it’s not the algorithm you have to look at, it becomes very interesting indeed. IMHO :)[/quote:5ec0ae7df4]

    This is very true I think. The other interesting aspect of it is what happens in really dynamic environments where the nodes are changing rapidly as the game progresses. For example, you go and construct this graph and then while the game is going on someone knocks over a wall (using the physics engine) and all sorts of nodes on the graph are no longer accessible or relevant. There are some dynamic pathfinding algorithms from robotics like D* which deal with this but I think they might be too computationally expensive to use in this context …..

  • #26858

    hugh
    Participant

    Actually the guy who wrote Tex was Donald Knuth, not Edgar Dijkstra … duh.

  • #26867

    peter_b
    Participant

    knuth also was the person who wrote about all the algorithms not dijkstra!
    Dijkstra pretty much did just shortest path a few other bits and pieces.

  • #26871

    hugh
    Participant

    knuth also was the person who wrote about all the algorithms not dijkstra!
    Dijkstra pretty much did just shortest path a few other bits and pieces.[/quote:d7095721fa]

    Yeah …… knuth was the guy who wrote the books I was thinking of.

    Dijstra did do a bit more than a few “bits and pieces” though :-) He wrote the original paper about why the GOTO statement was bad programming and consequently was largely responsible for changing entirely the way programming languages are written, invented semaphores and laid the foundations for all the formal verification theory in computer science ….. much of that not necessarily of all that much interest to people here maybe ….

  • #26928

    philippe_j
    Participant

    Well, you tell that to my first programming lecturer… the number of times he ranted at us for our “spaghetti code”. I think the first time he saw my first year project’s code he almost had a heart attack. I had essentially this huge switch statement… LOL :lol:
    I knew about the Tex language, but you confused me there for a moment. It is a pretty geeky thing to do, though. Very “Leonardo Da Quirm” in spirit, i think: “I need to type this memo, but my word processor can’t type this one mathematical character… mmmh, I need to invent a language to do that, this afternoon”. :lol:

    But more on topic: as you mention, what happens if the environment is dynamic? Well, that’s precisely the problem with a system like AAS.
    AAS does a lot of complex precalculations before run time, and is therefore not a good way of doing dynamic path finding. I don’t remember the specific here, but I expect you would do some sort of hybrid between the pure AAS and more node based system, but still.
    What I’d LOVE to know is how the Geonode (was that the name?) system used in Red Faction was developed.
    Now that I would have loved to see more of…

  • #26974

    darf_danno
    Participant

    Ok so from what I have gathered a good research topic would be to develop pathfinding for a dynamic environment where terrain and level shape can change?

  • #26975

    Skyclad
    Participant

    Is this for a final year project or a masters?

  • #26977

    erckle
    Participant

    Hey Danno,
    check out this white paper from RenderWare, It talks about Pathfinding in Dynamic Environments:

    http://www.csl.com/sales_sheets/ai_pathfinding.pdf

    Theres also another one on perception if your interested:

    http://www.csl.com/sales_sheets/ai_perception.pdf

  • #26981

    darf_danno
    Participant

    Is this for a final year project or a masters?[/quote:78ec56f2f7]
    Masters

  • #26983

    philippe_j
    Participant

    Actually, yeah, that sounds like a pretty good project.
    Interesting and more importantly, the lecturers (well, Mark Leeney and scant few others, really) would actually be able to follow you… :wink:

    The way I would have approached it myself (cos I’ve been thinking about it) would have been like the concept of “repaint regions” in Windows GDI, where you tell the program to repaint only a few portions of the screen. Something you never see (well, that I never saw) in proper graphic programming. Essentially, would it be doable to do the calculations that are done outside of runtime during runtime, if those calculations were limited to a very small area. I.e. I know I can calculate nodes (whether they are nodes or volumes like for AAS) when I am creating my map and “rendering” it, but if I only do this for that small bit that just got destroyed, could I do it real time?
    Say, if this wall is separating two movement volumes. If I blow it up, is it doable to create a new volume instead of the hole I just created, and connect that new volume to the previously unconnected volumes on each sides? Would it be too slow?

    I don’t know about you, but I think that would be a damn good project. Even if you didnt get it to run fast, you would learn a lot about the structure of 3D levels (binary partition) and pathfinding (the many approaches to feeding A* with a useful node network).

    Oh yeah, also don’t misunderstand the point : you are not trying to improve A*, but rather, you are trying to improve what’s being fed to it, the nodes, and how they are calculated. It all makes sense once you are familiar with it :wink:

    And despite the busy schedule of the PGDip, I don’t mind giving you a hand if you have a question.

The forum ‘Programming’ is closed to new topics and replies.