#14 pathfinder refactoring

open
nobody
None
5
2007-10-24
2007-07-11
Astrid Sawatzky
No

this is currently planned:

Entity has a PathGuide.
Entity calls PathGuide.getNext(currentPos, destination)

PathGuide has a Path
PathGuide uses PathFinder, CollisionMap
- if saved Path collides with another entity it has to be recalculated
(by PathFinder)

these are only ideas:
- PathCache has 1..n cached Paths (for different PathGuides).
* caching of different Paths or PathGuides
- ZonePathCache
* precalculated routes that can be used partly
(e.g. going by bus)

Discussion

  • ChadF
    ChadF
    2007-07-12

    Logged In: YES
    user_id=1668474
    Originator: NO

    Use Path instead. I did the initial work shortly before the cvs freeze a few weeks back. A path would be used to direct all GuidedEntity movements (including simple directions). The path would hide the details of how the path should be followed.

    The searchPath() methods should probably be changed to return an appropriete Path implementation (most likely FixedPath, but not required), or null when no path is found. Since everything that calls it either just checks it for no-path-found, or convertes it to a path.

    The current A* pathfinder impl ideally would go into it's own sub-package, implementing some core interface. Then other algorithms could be created (in other pckages) and plugged in and tested at will, transparent to the rest of the code.

     
  • ChadF
    ChadF
    2007-07-12

    Logged In: YES
    user_id=1668474
    Originator: NO

    Beyond what I mentioned in the IRC (assuming you read the logs already)..

    The basic movement design from an entity's perspective:
    Entity - No presumed notion of self movement.
    ActiveEntity - An entity that has direction and speed, but no control beyond that.
    GuidedEntity - An entity that extends the an active entity, but uses a Path for all it's movement.

    A path is like a Shape in awt. A shape may be a rectangle, polygon, or even a circle. While a polygon has the notion of specific points that make it up, a circle doesn't. So when drawing a shape, the shape does it's own rendering, since nothing else can know it's internals. So in the same way, a Path should be the nexus that tells the entity how to move.

    A path has it's notion of how to move an entity along, with an optional destination point (where known), so that it can hopefully be sent to the client side eventually as a hint of when to stop (and avoiding that snap-back visual). And maybe [where supported] a simple point list of it's effective path (but only the creature debug code really needs this right now).

    The bridge between your design and mine:
    A particular implementation of Path _is_ a PathGuide in effect. The GuidedEntity asks the path to point it in the right direction along the way, and the "guide" in the path does that work.

    You don't want to require a PathGuide, which is coded/linked to a PathFinder, all the time, since finding a path is generally unneeded for the fixed paths that NPC's use. Unless you assume the notion of a "fixed" PathFinder to avoid the search overhead, but then the same function of FixedPath exists, only with 2 extra levels of code.

    And before blaming me for walking on your code changes, please check the cvs history on recently changed files to make should you're not stepping on (and kicking) someone else's changes. I wanted to do the same thing you did with ripping out the unused pathfinder code when I did the other changes.. but once I looked at the cvs file logs, I saw that new files had been added semi-recently (in the past year), but not used.. so I opted not to delete them because I didn't want to risk abruptly trashing the changes someone else started and may have simply got side-tracked on (a common thing).

     
  • Danny Lade
    Danny Lade
    2007-07-15

    Logged In: YES
    user_id=888158
    Originator: NO

    The idea of the PathGuide is one of the real life:
    If you need to go to an unknown destination you will ask the next person for it. He can show you the way on the map or just describe it.
    A PathGuide could hold information about already known Paths from its Zone so they could be reused.

    In this model the Path would then just be a brainless data container that can tell you it's next step.

    On the other hand it is possible to give the Path a bit more brain and handle it's way by itself.
    The only problem is, that we lose the possiblity to cache already calulated Paths - because a Path can't cache itself.

     
  • Danny Lade
    Danny Lade
    2007-07-15

    Logged In: YES
    user_id=888158
    Originator: NO

    Another idea behind the PathGuide:
    In real life you don't ask just one Guide for a destination. If you got lost or forgot the way you asked the first person, than you ask a second one.

    Behind this scenario the idea is to spread some PathGuides other the Map/Zone. So you can easily render the way from one Guide to another and from there to the destination.
    These Guides could be placed on often used places.

    However, the pathfinding will fasten up for zones as longer as it runs.

    Example:

    ######
    1 #
    +++ ######
    G++++++G++++d
    +++ ######
    2 #
    ######

    1/2 - entity which like to walk to destination
    d - destination
    + - path
    G - good position for a PathGuide

     
  • Alex
    Alex
    2007-07-25

    Logged In: YES
    user_id=1811580
    Originator: NO

    Has anybody played the game Liquid War? The premise of the game is you control an army of pixels, which all take the shortest path towards your cursor at any given point in time. The basis is a pathfinding algorithm that is extremely efficient for many starting points and one endpoint (able to find the best direction for hundreds of pixels many times per second) In cases where many points have to follow one point, such as monsters attacking a player, using this algorithm seems like the best approach.

    Wikipedia has a page on shortest path algorithms, and the most promising from that look like A* and Dijkstra's. A* is a heuristic approach, which means it's super-efficient and usually correct. Dijkstra's algorithm is also quite efficient, and has that added bonus that it can find the path to multiple endpoints without reducing complexity (which means by swapping endpoints and start points, it can find the path from multiple start points to one endpoint, like the liquid war algorithm).

    My recommendation would be to generate a Liquid War-style mesh around all players at all times, use it for monsters that target the players, and also use it when the players move by reversing the resulting path. Also, I think the path should be calculated at each turn, because it is annoying when I have to double click my destination again because a monster stepped in the way and my avatar is trying to walk right through it.

    If you would like me to try to implement the pathfinding algorithms for Stendhal, let me know.

    Links:
    http://www.ufoot.org/liquidwar/v5/techinfo/algorithm
    http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
    http://en.wikipedia.org/wiki/A%2A_search_algorithm

     


Anonymous


Cancel   Add attachments