Pathfinder:Redesign

From FIFE development wiki
Revision as of 16:29, 1 June 2012 by Prock (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

This article is outdated and is just stored for archive purposes. Archived.png

This article became outdated and is just stored for archive purposes in this wiki. There are several reasons why an article could become outdated. The development team may have decided to use a different concept or even the author itself felt that the article is not really up-to-date with the current development status of the project anymore.

Proposal #2: Simple Single Layer Path Finding

In the proposal 0, the architecture to link the path finding AI and the main Fife code seems to be nice and clear. So here I will just fill in the AI parts.

1. The path finding algorithm (AI) should stay as an independent component as possible.That is to say, the input parameters should only take (starting point, target point, map related), and return a path to the Route Service Layer, which is a vector of coordinates. The path algorithm should not tangle with any instances in the game.

2. The path algorithm should still only handle single layer path finding. To solve the multilayer problem, we should introduce an adaptor, the adaptor will map coordinates (instances) at different layers and map it to a single layer. Whether this Adaptor should be a new component between Route Service Layer and AI, or should it be just in the Route Service Layer needs to be determined.

3. Also, for the AI component, I hope we could have more than one choice of algorithm, e.g. A*, dijkstra ... etc. We should be able to turn on the algorithm we want during compile time. Would this be possible in Fife?

  • One small note here is do we want to rename "Route Service Layer" to "Route Service Tier"? or some similar words for "Layer"? Just to avoid the cofustion between the layers for maps?


Proposal #1: Current State

This documents the current status (FIFE 2009.1). This shall only serve as help during the redesign.

The current pathfinder contains two pieces of codes: linearpather and routepather. Linearpather seems to be a left over of old code and it is not used in Fife anymore. Therefore, this document will focus on routepather.


PATHFINDER CLASSES

In trunk/engine/core/pathfinder

  • SearchSpace: The SearchSpace class is a dual of the Layer class. Each SearchSpace instance is corresponding to a layer instance. If a layer needs to be searched, a corresponding SearchSpace instance of that layer will be created. The main difference between the Layer and the SearchSpace classes is that the SearchSpace defines the area needs to be searched in the layer.
  • Heuristic: It is a class to calculate the cost function for the A* algorithm. There are two classes inherited from the Heuristic class: SquareGridHeuristic and HexGridHeuristic. SquareGridHeuristic is used for 4-neighbor cells. HexGridHeuristic is used for 8-neighbor cells.
  • Search:
    • a. The Search class contains the information required for each search action. The m_from attribute of the class indicates the start point of the search, and the m_to attribute indicates the end point of the search. Please note that the comments of these two attributes are contradicting to the corresponding comments in the constructor. The comment for the constructor is correct while the comment for the two attributes are wrong.
    • b. The Search class contains the SearchStatus enumeration and the m_status attribute. They are used to indicate the result of a search action.
    • c. Each Search instance has a m_sessionId.

In trunk/engine/core/pathfinder/routepather

  • RoutePatherSearch: The RoutePatherSearch class inherits from the Search class. It contains additional attributes compared to the Search class.
    • m_spt: It is a pointer to a vector of integers, which is the shortest path tree.
    • m_sf: It is a pointer to a vector of integers, which is the search frontier.
    • m_gCosts: It is a pointer to a vector of floats, which is a table holding cost values.
    • m_sortedfrontier:
  • RoutePather: The RoutePather class inherits from the AbstractPather class. It has a few additional functions:
    • cancelSession(): Cancel a RoutePather session
    • addSearchSpace(): Add a search space to the RoutePather
    • addSessionId(): Add a sessionId (for the new instance) in the RoutePather
    • makePlan(): Find the path for the given instance.
    • m_sessions: It is a SessionQueue. The SessionQueue is a PriorityQueue. It stores all the session (search) of the game. Each session has a corresponding id.
    • m_searchspaces: It is a SearchSpaceMap. It maps the pointer of a Layer instance to the pointer of the corresponding SearchSpace instance.

MODEL CLASSES

The PathFinder classes use classes in Model

In /trunk/engine/core/model/metamodel

  • AbstractPather: An AbstractPather is the abstract class for all pathers. A pather belongs to a model, and it has a function getNextLocation(), which is called by the model to determine the next location of an instance. A pather stores multiple sessions for multiple simultaneous searches. These multiple searches come from multiple instances.

In /trunk/engine/core/model/structures

  • Instance: Instance is a class defined in engine/core/model/structures. It is created as a dual of another object.
  • InstanceTree: A data structure to store instances in a specific layer.
  • Layer: A layer of the model.
  • Location: Location is a class defined in engine/core/model/structures.
    • m_layer: is pointer to the corresponding layer of the location.
    • m_exact_layer_coords: is an ExactModelCoordinate of the location on the corresponding layer.
  • Map: Contains a list of pointers to all layers in the game model.

UTILITY CLASSES

While documenting the pathfinder, I realized it uses a lot of codes from other parts of Fife. Therefore, I am doing some additional documentation here for other source codes used by the pathfinder.

In /trunk/engine/core/util/structures

  • PriorityQueue: It contains a list of elements, while each element (called value_type) is a pair. The first value of the pair is the index, and the second value indicates the priority of the element.
  • A game model contains a list of pointers to maps, and each map contains a list of pointers to layers.

PATHFINDER SIMPLIFICATION

1. Remove InstanceTree. The only time the InstanceTree was used is to check where the location is occupied by other instances. This data structure seems to me an over design for what it needs to do. Instead, each layer can just have an instance occupied array. The array (link to a 2d map) is only 1 or 0. 1 means the cell is occupied.

2. Get rid of LinearPather. Combine Search and RoutePatherSearch to one class. The new Search class should be a member class of the RoutePather class.

3. Since each SearchSpace is corresponding to a Layer. There is no need to have SearchSpace. We can move its functionality to the Layer class.


Future: Futher Questions and Discussions

1. Can we embed the sessionId inside the Instance?

2. How to determine the sessionId of an Instance?

3. I am thinking maybe we can get rid of this Location class? This might be a good first step of re-design the Fife pathfinder. Each Location would be replaced by an universal coordinate.

4. Each Instance object is a dual of an Object object. It seems to me this doubled the number of objects in the memory. Can we just keep one copy?