I would suggest not storing a reference to the map or storing the tile coordinate in the tile. The map should be the one doing all the logic so individual tiles should only be a tiny set of data.

I just mean the tiles themselves don't need to know the object they are contained in. I wouldn't advocate trying to take the functionality entirely out to a standalone method.

I may have partially misunderstood. Are you talking about the pathing nodes used during a path search or the tile nodes of the tile map?

I don't think the tiles of the tile map should need a pointer to the map, or know their location within the map. For pathfinding purposes, the 'PathNode' needs something that maps back to its location in the map so that it can expand the search at each iteration, but that can be properties specific to the PathNode and not the TileNode. That is, assuming you are not using the tile nodes directly in the pathfinding, which I would not recommend, since the pathfinding needs a set of data specific to the search that has no reason to be persistent with the tiles(g cost, f cost, parent pointer, etc).

I tend to write standalone objects as interfaces to pathfinding that are allocated per AI that are basically their navigation interface.

// for each AI

Navigator * nav = navmesh->AllocPathQuery();

nav->FindPathToGoal( pos, myCapabilities );

// incremental updates for tim splicing

switch( nav->UpdateSearchStatus() )

{

case PathFound:

{

// get the string pulled corners

NavCorner corners[4];

const size_t numCorners = nav->GetNextCornersInPath( corners, 4 );

if ( numCorners == 0 )

{

StopMoving();

}

// update AI steering/velocity with the corners

break;

}

case PathNotFound:

// print error, etc

break;

case PathSearching:

break;

}

I usually allocate it through the specific pathfinding system and it maintains a reference to the data classes it needs to function. I've also had good luck abstracting these Navigators around the concept of 'corners'. A base Navigator class can take and provide access to a generalized representation of the path, while several implementation subclasses may be available for different navigation systems NavigatorTileMap, NavigatorNavMesh, NavigatorWaypointGraph, etc. In all these cases, the specifics of the pathfinding and interaction with the specific navigation system can be contained in these subclasses while the interface provides general access to the string pulled corners of the path, with edge flags and node flags that communicate information about the underlying path, such as the types of polygons and such traversed.

The navigator subclass, such as the NavigatorNavmesh, is indeed tied to the navigation mesh. It's an implementation of my interface where it is tied closely to how the navigation mesh stores data. The Navigator is my path finder and my path smoother. This object serves several purposes for me. It represents the state of navigation for a particular entity. The navigators could be updated from multiple threads, modifying their internal search state and referencing the navigation mesh in a read only manner, they could be updated serially in a time spliced sort of manner(allowing many paths to be in progress simultaneously), and it shields the rest of the code from the choice of navigation system I'm using, allowing me to change it easier at a later point. Also, since it maintains its own internal state which may involve functionality closely related to the navigation system, it can handle the dynamic aspects of path following was well, such as string pulling, often implemented in a way that requires regular maintenance of the path which can be encapsulated in the navigator.

You don't have to do it this way. You can just create a function on your map class or something if you want to start simple that solves a path and gives you back an immediate result in the form of filling in a result object or a list of path nodes, etc.

Status TileMap::FindPath( PathResult & resultOut, const vec2 & src, const vec2 & dst, ... );

Path nodes hold the state of the navigation query at a particular state, the code, the parent pointer for reconstructing the path when the goal is found, etc. This is temporary scratch data and doesn't belong in the same objects as your Tiles, which presumably hold a reference to the image used for that tile, whether the tile is solid or not. I think about the tile map in a 2d game as an image, and the tiles as the pixels of the image, the color channels as the data about those tiles. I would not bloat that data with pathfinding search state. Other than bloat, if the tile map, of which there is presumably only 1 copy of, contains the search state, you can only solve for 1 query at a time.

I would suggest, even if you keep it as a simple function call for an immediate path solution and nothing fancy like a navigator, that you keep the search state separate from the tiles.

something like

struct PathNode
{
    int x,y; // coordinate of node in tile map

    // search state
    PathNode * mParent;
    float g, f;
    ....
}

As long as the tile maps aren't huge, if it's dynamic allocation you want to avoid I would allocate a pool of 2d pathnode arrays of the same size as the tile map. Then the only potentially dynamic aspects of the pathfinding is the open list.

The overhead of the nodes is certainly in additional memory, but you gain much more than you lose by being able to thread out the searches, or incrementally update multiple searches at the same time.