Path-Finding

    This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

    • PathFinding

      Hi,

      I've see a few tutorials and some source code on this
      topic.

      A* ("A-Star") is a specific pathfinding algorithum that
      one can use. The idea is to break up your world into
      search grids which leads you to a 2 dimensional array by
      which you can perform your search. Is this something
      you want to do in a large 3D map? I can see where you
      can use it in a map that might be an 2D array and your
      building your world from array (Pacman game), but in a
      3D world where you using meshes (i.e. Halo, BF, UT)?
      Can you even do this and how would you break up the
      world into grids. I would think that would be a problem.


      Thanks,
      Sabrina
    • It's not just a 2D grid thing. The samples use a 2D grid because it's easier to explain that way.

      Pathfinding is essentially finding your way from one node to another via connected nodes. In the case of those tutorials, the nodes happen to be represented as adjacent squares.

      In practice, those nodes don't have to be 2D squares. They can be actual points connected by lines... or better yet, adjacent triangles... as in the triangles that make up a 3D mesh used to represent the ground on a hallway or a complex building.

      3D games typically use what's called a "navmesh", which is basically a bunch of triangles, invisible in the game world, used to help an A.I. draw a connection (jumping from triangle to triangle) from one place in the world to another. A* tends to be the optimal choice for this type of pathfinding because it is goal oriented.
    • RE: PathFinding

      If I were going to use A* in a navmesh I'd probably make an STL map-like structure and use it to track which faces connect to which other faces. Then you could walk the structure fairly quickly to find a path based on whatever weighting criteria you like.

      Of course, all of the Game Programming Gems books have something or other about pathfinding it them. The method I described above is probably slower than the solution in GPG 1 for 3D pathfinding....

      Rich
      "Your job is not to die for your country. Your job is to make some other poor sod die for his."
    • Yes, Game Programming Gems vol. 1 was what introduced me to the wonderful world of pathfinding. This was a really a neat thing to get into... I highly recommend it.

      I was looking for a multinode STL structure for this purpose, but I don't think there is one that directly represents a graph of connected nodes such as the one used for A*. You'd basically have to make your own two classes for this sort of thing.

      One class would be the node class that has a list of pointers to adjacent nodes... you can also consider this as representing a single triangle/square that has a list of pointers to adjacent triangles/squares. I suppose that list of adjacent nodes can be an STL vector or list, depending on how dynamic you want your graph to be.

      The other class would be a graph class that holds all of these nodes as a representation of the world that AIs can travel. The most important function of the graph class will be the accessor that gets you a specific node based on some data input like xyz coordinates. This gives the pathfinding algorithm a means of having a starting node and an ending node. I guess this might be where you might use std::map or hash_map if you inserted nodes with a keyname or something. I couldn't think of a naming system for those trianlges in the navmesh, so I used std::list or something like that to hold those nodes together and just paid for the cost of iterating through each node to find the one that matched my needs (closest to the given xyz coordinates).

      Those samples that used a 2D grid to illustrate the algorithm got rid of that first node class and simplified the second graph class.

      Tangent (probably pointless) Remark: I love smart pointers ... a lot... but these two classes are definitely not the place to use them. These algorithms can be very expensive and you want as little overhead as possible. Plus this arbitrarily interconnected graph of nodes can be a circular dependency nightmare.
    • Hi,

      Thanks for the comments. My next question was going
      to be what would be the best way to implement
      a A*, but Kain answered itt. I too was thinking
      about the std::list, std:map, etc. but I was
      concerned about the iteration factor. I was doing some
      research on how the 'pros' do it and came across the
      HalfLife-2 source code, found here.

      hl2doxygen.sniperumm.co.uk/files.html

      They too have a pathfinding implementation and its a bit
      complicated for me to follow. I can't see if the author(s)
      are using the stl::map, stl::list, etc. I would imagine they
      implement their own type of maps, lists, STL, etc. Of
      course this is pretty comlicated stuff, and I would not
      want to do something this complicated.

      I did find the link to gameai.com several months ago,
      some of those links are dead now. The searches I have
      found don't really mention implimentation or address
      concerns that for example Kain pointed out.

      Can I use the std::map, std::list, blah and implement it
      as a tree structure to avoid the "linear iteration"?
      (I think they call it O(n) and I want something like a
      O(Log N), right? )


      Thanks,
      Sabrina
    • Originally posted by Sabrina
      Can I use the std::map, std::list, blah and implement it
      as a tree structure to avoid the "linear iteration"?
      (I think they call it O(n) and I want something like a
      O(Log N), right? )

      If you use std::map, then it is already a tree structure. std::map is a binary search tree under the hood, which is O(Log base 2 of N), as you already pointed out.

      But, I don't think you can get any better than O(N) because the tree only works if you have a proper key that allows you to find the searched value with only operator== and operator< defined. In the case of finding the proper node in pathfinding, you typically need a fuzzier test such as "is this point inside a triangle". Because this test is an if-statement, you're going to have to iterate through each node in O(N) fashion until that test is succesful.

      So in short, you won't get any benefit from representing the interconnection of nodes with a std::map.

      I think I remember you saying you were doing Pac-Man, right? If that's the case, triangles may be overkill. You can represent the pathways in a pac-man map using only points and lines. Basically, every intersection on the map is a point with lines coming from it. A T intersection (node) has 3 lines coming from it, and therefore 3 adjacent intersections (nodes). Your tests should be faster, this way, but you're still going to need some function that asks the graph to "give me the nearest two nodes to my start and end targets." But then, I think the original pac-man did not have true pathfinding as much as they used patterns and weak proximity detection... not sure, though.
    • Perhaps doing the test for which node you occupy should come before the actual pathfinding search. You'd want to pass in where you are and where you're going. So, first, test which tri (or whatever you use) you occupy. Next, locate the destination node. Pass these to your search function.

      STL::map is not the best structure for this purpose, but it's not too bad. Data Structures for Game Programmers has some good pointers on searching and sorting, and other data tricks - including pathfinding. Anyway, as long as you have some sort of way to associate each node with it's adjacent nodes and (if you need such a thing) the cost to enter these nodes, you're good. Game AI by Example also covers pathfinding extensively and points out ways to make the movement on a nav-grid-like structure of points more natural.
      "Your job is not to die for your country. Your job is to make some other poor sod die for his."
    • Thanks Kain and Nebuchadnezzar for clearing up that
      for me. I've seen some code/docs and they talked about
      using trees and lists, but I was not sure on the best
      implementation. I just assumed that a tree structure
      would be the best implementation. Thanks for clarifying
      that for me! :)

      The Pacman is somewhat a lost cause at this point, or
      should I just say on hold for now. I have a list of
      recommended books from this web site that people
      have been suggesting to get and read.

      You lost me Kain on the points, lines, and intersections
      in pathfinding. Again, I will need to get the books to read
      further. If you should know of any web sites that address
      this, please let me know.

      "Navmesh"... Hummm that's a term I have never heard before, again I will refer to some books.

      Thanks again for your comments and input :)


      SM
    • Why get books when you have this forum?

      hahahahahahahahahahahahahahahahaha!

      Just kidding.

      Points and lines, eh? Well, here's a rundown:
      1. The purpose of pathfinding is to show an AI a series of dots that will take it from one place in the world to another
      2. The data for pathfinding is always the same... a representation of the entire walkable world made up of connected elements.
      3. In 3D games with mountains and stuff, these connected elements are usually made by the artist. 3D artists work in triangles. These triangles make up the 3D navmesh. In this case, the data for pathfinding is made up of triangles connected to each other that make up the world. Each element triangle has a maximum of three neighbor triangles.
      4. In 2D tile-based games, the connected elements might end up being squares. In this case, the data for pathfinding is made up of squares connected to each other instead of triangles. Each square element has a maximum of three neighbor squares
      5. Elements with connections... they don't have to be squares or triangles. They can be anything you make of them. So how about replacing triangle/square with points? Let's say you're a masochist, and you don't want an artist making a navmesh for you. Then the alternative is to have a designer place invisible points on a map and specify which points are connected to which other points. This is often called the waypoint node method. So a single hallway can be represented to the pathfinding system as two points that are considered to be connected to each other. Each point would exist at each end of the hallway.
      6. An AI following a waypoint-connected path is basically just running to the next point in its list. Eventually, all pathfinding code ends up working this way. Those waypoint nodes can be placed by the designer in data, or dynamically created by the code after it calculates an optimal path with the given triangles or squares. The AI always ends up chasing the next dot, and when it reaches that dot, it moves on to chase the next dot in the list if there is one.
        [/list=1]