FIFE forums

Please login or register.

Login with username, password and session length
Advanced search  

News:

FIFE 0.4.0 has been released on 15th of January, 2017!

Pages: [1] 2

Author Topic: Pathfinder Rework  (Read 9382 times)

wenlin

  • Newbie
  • Posts: 23
    • View Profile
Pathfinder Rework
« on: April 09, 2009, 06:46:19 pm »

Hi all,

As in the last meeting, the pathfinder rework was brought up, I decided to list some of my suggestions/questions I noticed while working on the ticket 234. Please feel free to post your opinions and list items not mentioned here. Maybe after we agree with the topics discussed here, we can start another discussion on how to design the architecture in the new pathfinder code.
 
1. It seems to me that "linearpather" is not used anymore. At least, it is not used in the rio_de_hola project. Therefore, if it is not used by any other project, we should be able to get rid of this.

To do: If anyone knows any project which still use "linearpather", please bring it up.

2. Right now, each layer has its own layer coordinates (and some with exact layer coordinates). So when we need to compare coordinates from different layers, we need to convert the layer coordinates from one layer to another. For example:

 CellGrid* cg1 = m_searchspace->getLayer() -> getCellGrid();
 CellGrid* cg2 = anotherLayer->getCellGrid();
 ModelCoordinate anotherLayerCoord= cg2->toLayerCoordinates(cg1->toMapCoordinates((*i)));

 Notice that we can only use layer coordinates instead of exact layer coordinates during this kind of coversion and we lose the coordinate precision during this procedure.

Suggestion: For each instance, besides its layer coordinates, it should also store an absolute game map coordinates (of course,we would need to define the absolute coordinates for the game first). This will make searching blocking objects (especially between different layers) and finding path a lot more easier and efficeint.

3. Currently, the decision of the final path depends on the calculation of heuristic. Due to the lack of documentation, I personally not really sure what it is calculating. It would be great if any one who knows what heuristic is calculating can share his/her knowledge with others here. Any related link/documentation/suggestion is also helpful.

To do: Please share what you know about the heuristic calculation in the code, including any related link/document/suggestion with us.

4. As phoku mentioned, the session part is sort of over-designed. I do have the same feeling as well. However, do we want to totally get rid of the session thing or do we want to keep part of it.

To do: If you have an idea about the logic of current session code is doing, please share your opinions about which part of this design we should keep.

Thanks a lot!

wen.
Logged

phoku

  • Developer
  • Full Member
  • *
  • Posts: 102
    • View Profile
    • IZ dev blog
Re: Pathfinder Rework
« Reply #1 on: April 11, 2009, 06:05:46 am »

Hi wenlin,

thanks for taking a broader approach to the pathfinding issues with FIFE :)
I have promised to take a closer look at that problem space too, but haven't
as of yet - so take everything I say with the prerequisite graine of salt.

1.) No opinion.
2.) Areed - a function should exists which would return the coordinates
of any instance in absolute world coordinates.
3.) Heuristics are metrics on the grid. In short we have to metrics which correspond to
allowing diagonal and NOT allowing diagonal movements. Having these is necessary for the
A* algorithm. (E.g. (0,0)-(1,2) gets either 3 wiothout diagonal moves (one move (+1,0) and two moves (0,+1)) or
2.41 with diag. moves ( one move (1,1) and one move (0,1)).

Actually the implementation is a bit overblown and at the same time limiting: E.g. usually one can supply a functor
with a function cost(A,B) that would return a float (including infinity) for the movement cost from A to B.

4.) Yes.

--

Alright ... I'll not go on and try to convey my (incoherent) ideas here.
I propose we take this page: http://wiki.fifengine.net/PathfindingArchitecture
and use it to redesign the way pathfinding is handled. Deal?

Just to give a bit food for thought:

How is multilayer blocking supposed to work anyway?
Should the cell outline of one layer be projected on another one?
Should it only work if the grids are the same?

Should it be handled within the current FIFE map model at all?
E.g. would a separate logical map of a blocking (and later
transparent) value suffice? These can be filled by intercepting
instance creation and deletion on all layers.

-phoku

Logged

wenlin

  • Newbie
  • Posts: 23
    • View Profile
Re: Pathfinder Rework
« Reply #2 on: April 13, 2009, 06:54:14 pm »

Hello phoku (& all),

It is great that we could have http://wiki.fifengine.net/PathfindingArchitecture to put our path redesign. It's just I don't have a permission to edit the page yet, so I will still post my ideas here in the forum for now.
 
Regarding "how is multilayer blocking supposed to work?", here is what I think:

First, each instance should have a few more attributes as follows:
Instance:
 1. int, layer id --> the id of the layer where the instance locates
 2. Set<int>, the set of interacting layers id --> the id of all layers where the objects there would block (interact with) the current instance.
 3. global coordinates

Then we should be able to handle the multi-layer and multi-grid object blocking (interacting) with the following design:
 For example:
 layer 1 with cell size 0.5x0.5
 layer 2 with cell size 1x1
 layer 3 with cell size 2x2
 
 Assuming an user controlled character Hero is in layer 2.
 A small blocking rabbit is in layer 1, and a big blocking bear is in layer 3.
 Then when a player clicks the mouse, a target for Hero is assigned.

 To get a path for Hero, we have:
 Hero.getPath(currentPosition, targetPosition);
 
 the getPath() should basically try to find a path in layer 2 (Hero's layer).
 The path is a vector of layer 2 cells (let's call it pathVector), and then the only thing we need to take care of
 here is: everytime when we add a new cell point to pathVector, we need to check if this specific cell is blocked in all layer.
 This should be easy since each object in all layers now have global absolute coordinates.

 So the main thing left is to have an algorithm to locate a path. This way, the old design of session can be abandoned. I don't know if anyone has any path finding algorithm in mind? If not, maybe I will post what I think for now, and people and discuss from there?

wen.
Logged

mvBarracuda

  • Administrator
  • Sr. Member
  • *
  • Posts: 411
    • View Profile
Re: Pathfinder Rework
« Reply #3 on: April 14, 2009, 12:26:01 am »

The wiki article is not protected. Simply register an account at the wiki, activate via confirmation email, log into the wiki and you can edit it.
Logged

zyrano

  • Newbie
  • Posts: 8
    • View Profile
Re: Pathfinder Rework
« Reply #4 on: April 14, 2009, 03:49:38 am »

For hints on routing see:

de Borg/van Kreveld/Overmaas/Schwarzkopf : Computational Geometry. Algorithms and Applications,
To understand this you need at least basic understanding on algorithmic concepts.

If you are new to algorithms (and plan to code something where algorithms are needed) see
Cormen/Leiserson/Rivest : Introduction to Algorithms as introduction. But take a few weeks at least to get some basic principal understanding on algorithms.

On one side, constraints have to be known to check what kind of algorithm/ how it can be implemented. On the other side it makes absolutely no sense to design an architecture without knowing the requirements of routing algorithms (especially the one which should be implemented).

So first decide, what you expect from the algorithm of your choice and what of information is available for routing (or could easily be made available), then choose the algo and implement it.

zyrano
Logged

mvBarracuda

  • Administrator
  • Sr. Member
  • *
  • Posts: 411
    • View Profile
Re: Pathfinder Rework
« Reply #5 on: April 20, 2009, 10:39:45 am »

A little question concerning the pathfinding code. We played around with blocking in PARPG today and we wanted to use diagonal movement for the agents for testing purposes. We changed the pathing attribute of the object layer from: pathing="cell_edges_and_diagonals"

To: pathing="cell_edges_only"

It seems that the pather ignores this attribute and you can still walk from one tile to another diagonally.

Furthermore it would make sense from our point of view to offer a "diagonals_only" option so that agents can only walk diagonally (NE, SE, SW, NW) but not over the cell edges (N, E, S, W). Could anyone verify that the pather currently ignores the pathing layer attribute?

I am actually a bit confused if cell_edges_only means N,E,S,W or or NE,SE,SW,NW movement. Could somebody clarify the intended behaviour as well?
Logged

vtchill

  • Developer
  • Full Member
  • *
  • Posts: 206
    • View Profile
Re: Pathfinder Rework
« Reply #6 on: April 21, 2009, 09:00:24 pm »

I did a little testing with the pathing when writing the map loader and i also saw that the cell_edges_only and cell_edges_and_diagonals seemed to do the same thing.
Logged

wenlin

  • Newbie
  • Posts: 23
    • View Profile
Re: Pathfinder Rework
« Reply #7 on: April 25, 2009, 05:52:07 pm »

After some thinking and research, I think maybe the best path finding algorithm we should use is the A* algorithm http://en.wikipedia.org/wiki/A* . It seems that the old code is also based on this algorithm (but I am not 100% sure). We should include multi-layer blocking in the new implementation. Any other idea other than using this A* algorithm?
Logged

vtchill

  • Developer
  • Full Member
  • *
  • Posts: 206
    • View Profile
Re: Pathfinder Rework
« Reply #8 on: April 25, 2009, 10:34:32 pm »

After some thinking and research, I think maybe the best path finding algorithm we should use is the A* algorithm http://en.wikipedia.org/wiki/A* . It seems that the old code is also based on this algorithm (but I am not 100% sure). We should include multi-layer blocking in the new implementation. Any other idea other than using this A* algorithm?

As far as I remember the current implementation does use an A* approach with a heuristic that is not super flexible to allow the user to define their own cost functionality.
Logged

wenlin

  • Newbie
  • Posts: 23
    • View Profile
Re: Pathfinder Rework
« Reply #9 on: April 26, 2009, 04:04:04 pm »

Hi vtchill,

"As far as I remember the current implementation does use an A* approach with a heuristic that is not super flexible to allow the user to define their own cost functionality."

So why do we want to allow the user to define their own cost functionality? Any special reason for that?

wen.
Logged

zyrano

  • Newbie
  • Posts: 8
    • View Profile
Re: Pathfinder Rework
« Reply #10 on: April 27, 2009, 12:54:26 am »

A* won't give a better result than an simplier implementation of Dijkstra's algorithm. The only advantage of the A* is that with a good approximation of the shortest path (for the heuristic) A* is a bit faster. But I think that for the FIFE engine games are split in sectors kinda like in Fallout 2. So for routing you only have to consider the sectors where player's characters are in. And routing with a few hundreds or thousand of objects is no problem for an actual pc.

For example I used Dijkstra's algorithm for routing in mass transit systems with over 1500 Stations and over 20.000 tours from which the ones which to take have to be selected. The data also included a few hundred footways and some other data to consider when routing.
With holding all the data in memory it needs in average about 100 milliseconds to do a routing on a usual dual core cpu. And that is with Java (maybe that makes no big difference today, I don't know).

With kind regards zyrano
Logged

mvBarracuda

  • Administrator
  • Sr. Member
  • *
  • Posts: 411
    • View Profile
Re: Pathfinder Rework
« Reply #11 on: April 27, 2009, 05:21:34 am »

To clarify: FIFE does use A* at the moment. There might be little need to change the algorithm itself as we heavily based our code on the open source A* implementation Micropather:
http://www.grinninglizard.com/MicroPather/index.htm
Logged

zyrano

  • Newbie
  • Posts: 8
    • View Profile
Re: Pathfinder Rework
« Reply #12 on: April 27, 2009, 07:02:24 am »

If you have an always working solution which is flexible enough, there's no need to change it. But if the given solution is not flexible enough for user defined routing,the implemenation of Dijkstra's algorithm is not so complex. Most of the complexity and headache when testing comes from adapting the algorithm to the own data model.

SimplyDijktra looks like
(let graph G = (V, E) with v in V are Vertices and e in E are edges)

Dijkstra(G, w, s)
1. Init
S = empty set /*handled stations are stored here in*/
Q = V[G] /*a priority queue filled with the vertices from G, order depends reachability, see hint below*/
while Q != empty set
  u = ExtractMin(Q)
  S = S union u
  for each vertex v which is neighbour from u
    relax(u, v, w) /*expanding edges, adapting Q,...*/

See introduction to algorithms, second edition, page 594 and following for more information about that.
But as you can see from this, the algorithm is really simple and if it matches the data model it's easy to implement. It took me a few hundred lines to implement this cause the data model I had in this case was more complex than the code above assumes.

 I don't know anything about Micropather, so I can't judge about it.
Sorry if my hints aren't helpful but I've enough to do and have not the time to learn C/C++ to work through the code by myself.
« Last Edit: April 27, 2009, 07:06:46 am by zyrano »
Logged

mvBarracuda

  • Administrator
  • Sr. Member
  • *
  • Posts: 411
    • View Profile
Re: Pathfinder Rework
« Reply #13 on: April 27, 2009, 07:09:41 am »

No problem zyrano :-) Your feedback is appreciated.
Logged

wenlin

  • Newbie
  • Posts: 23
    • View Profile
Re: Pathfinder Rework
« Reply #14 on: April 27, 2009, 03:27:56 pm »

Hello,

I looked into the code in http://www.grinninglizard.com/MicroPather/index.htm
It seems that the current Fife pathfinder didn't just copy the code, it did sort of re-code it in Fife.

I read A* and dijkstra's algorithms again, both should not be too difficult to implement. However, I didn't find any data showing which algorithm would actually perform better for which type of game. So here is what I propose: we set an PathFinderAlgorithmEnum = {Astar, Dijkstra, ... }, then the user (the actual game developer) can switch to whichever the algorithm they want to use in their game. For example, PARPG can choose to use Dijstra while Zero might choose to enable Astar.

I believe it would also be a good contribution as an open source project to provide some real time comparison for different path-finding algorithms. Once we set up the code structure for the first algorithm, all additional algorithms should take little time and effort to code.

A similar strategy can be applied on the heuristic cost functions as well. We can implement a few common HeuristicFunctionEnum = {Manhattan, Diagonal ...}, then it's up to the game developer to choose which one they want to use.

How do you guys think?

Wen
Logged
Pages: [1] 2