Pathfinder:Architecture

From FIFE development wiki
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.

Pre-Python

This is the old (ancient?) proposal, implementation status unknown.

Overview

The purpose of this article is to outline the architecture of a pathfinding solution and how it fits into the FIFE code base. I think it is a little over the top to talk about this solution in terms layers, but I find it a useful way to separate areas of responsibility and code. So I'm going to talk about this solution in terms three layers: the Route Service Layer, Map Adapter Layer and Generic Solver Layer.

Roughly speaking each layer will correspond to a directory (package) of closely coupled classes (files) that loosely depend on the layer below, the following diagram outlines the responsibility for each layer.

PathfindingLayers.png

Route Service Layer

The most important part of this design is the Route Service Layer as this provides the interface used by AIs to request pathfinder or path following services. These typically will take the form of: get me from X to Y and tell me once I get there, or tell me I can't get there.

Internally this will be implemented in the form of a conversation between the Route Service Layer and the Map Adapter Layer something along the following lines:


-> Find me a path from X to Y.
<- Path = X, A, B, C, D, Y
-> I'm now at A ( Path = A, B, C, D, Y )
-> I'm now at B ( Path = B, C, D, Y )


Something changes on the map, trigging a re-planning of existing paths.


<- Updated Path = B, E, D, Y
-> I'm now at E ( Path = E, D, Y )
-> I'm now at D ( Path = D, Y )
-> I'm now at Y ( Path no longer needed )


The idea being each AI is holds an (owning) reference to a Route object while the AI is trying to reach a given destination. This Route object will change over time as the AI is moved along its path or if the path becomes blocked and is re-planned.

The Map Adapter Layer will also holds a (weak/ non-owning) reference to each Route object that is currently being used by the Route Service Layer. These will be used to efficiently re-plan in progress paths following changes to the map.

I'm expecting the Route class will expose the the following interface for use in the Route Service Layer:

class Route
{
  public:
    typedef Something          NodeType;
    typedef SomethingElse      ConstPathIteratorType;

    /* Query the nodes currently in this route using STL style iterators, without travelling along it */
    ConstPathIteratorType  begin() const;
    ConstPathIteratorType  end() const;

    /* Move along the Route shortening it, returning the next step node */
    ConstPathIteratorType stepCompleted();

    /* State testing queries */
    bool hasSolution() const;         // check if this pathfinding is complete and found a solution
    bool isSolving() const;           // check if pathfinding is searching for a solution
    bool hasBeenReplanned() const;    // check if this Route has been re-planned

    /* Misc */
    void clearReplannedFlag(); // Clear the re-planned state of this route
    unsigned int length();     // Query the remaining length of this route
};

Alternatively the Route objects can be exposed directly to AIs allow them to control rate of movement and choice of animations more directly on a step by step basis.

Map Adapter Layer

The Map Adapter Layer is responsible for the following tasks:

  • Building map graphs that describe the map in a form the solver layer can understand.
  • Observing changes on the map that effect the map graphs and feeding these changes into the graph.
  • Tracking all the "in-progress" paths and trigging re-planning as appropriate.
  • Scheduling any re-planning within a limited CPU budget, possibility queuing re-planning to limit CPU usage.

Solver Layer

The Solver Layer is at the moment an abstraction of a graph based solver, at the moment this is slanted towards a solving a slowly changing map with no support for very transient blocking entities such as critters.

At the moment I see most of the approaches outlined in the Pathfinding as belonging to this layer.

Implementation Approach

After some discussion on IRC, I'm intending to re-think how best to support for blocking by fast moving entities (such as critters) However I suspect solutions can be worked into this layers approach by mainly changing the Map Adapter layer.

Given the complexity of path finding I'm going to suggest we start developing using this outline until have a working AI path finding. Then once the feature is working measure the CPU cost of various path finding scenarios and consider replacing it with a more complex solution that support multi-level path finding. Basically a make it work, then make it work faster.