Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Don't forget to read Tuesday's email newsletter for your chance to win a free copy of Construct 2!


Are there alternative methods of obtaining neighboring nodes of a node from a 2D grid-like Map of nodes?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 tom_mai78101   Members   -  Reputation: 575

Like
0Likes
Like

Posted 17 December 2013 - 01:45 AM

While creating my pathfinding system for a 2D grid-based Map of nodes, I'm wondering if I can omit off having to pass the Map object as a parameter to all of my Node objects. That way, I can make my Map of nodes flexible and without having to worry about re-initializing all of my Nodes with the Map object all over again.

 

Given that there's a Node at position (X, Y), I was thinking of fetching its neighboring nodes, (X-1, Y-1), (X, Y-1), (X+1, Y-1), (X-1, Y), (X+1, Y), (X-1, Y+1), (X, Y+1), and (X+1, Y+1), without having to go search for it from the Map object. It turns out to be nearly impossible to do, since I don't have anything to refer to and make relative calculations based on (X, Y) alone.

 

Does anyone else know alternative methods of obtaining neighboring nodes from a specified Node position, without having to refer to a Map object containing all of the Nodes? If there are none, is that why I can't write off the reason for passing the Map object as a parameter to my Nodes?



Sponsor:

#2 Nypyren   Crossbones+   -  Reputation: 4498

Like
0Likes
Like

Posted 17 December 2013 - 02:25 AM

The alternative is to give each node a link to every neighbor. But that would be MUCH more memory-hungry than if you have a regular grid of nodes as a single 2D array. If your map is not a regular 2D array, then having node-to-node linking might be OK.

With a 2D array, your nodes do not need to link to their neighbors OR link to the map. If your algorithm passes the map as a function argument (or otherwise keeps it in scope in some other way), you will always have the map available to perform neighbor lookups without having to look it up from the node each time.

Edited by Nypyren, 17 December 2013 - 02:30 AM.


#3 DrEvil   Members   -  Reputation: 1105

Like
1Likes
Like

Posted 17 December 2013 - 02:54 PM

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.



#4 tom_mai78101   Members   -  Reputation: 575

Like
0Likes
Like

Posted 17 December 2013 - 07:47 PM

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.

 

Is that how it's supposed to be? I always get the inference that small data types may also need to incorporate large data types by either using callbacks or parameters passing.

 

And can you separate the logic out of the map and node data types into a static invocating method, so it becomes easier to call the pathfinding system wherever possible?



#5 DrEvil   Members   -  Reputation: 1105

Like
1Likes
Like

Posted 18 December 2013 - 08:15 AM

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.



#6 tom_mai78101   Members   -  Reputation: 575

Like
0Likes
Like

Posted 18 December 2013 - 09:14 AM

Both. In my case, the path nodes on a map is the same thing as tile nodes on the same map.

If tile nodes aren't supposed to see the object the nodes themselves are contained in, I'm curious that some demos or simple pathfinding tutorials will want to incorporate the use of passing the container in as a parameter, thus the tile nodes are able to see where exactly it is located. You're the first to tell me that this isn't always the case.

I also see from your example, a navmesh can generate a Navigator. This navogator object is then used to query a path from the pathfinding system, which is the Navigator.

Is this how it should be done? By UML, navmesh <- navigator, and navmesh <- list of nodes?

Which means the navmesh (Area) should contains both the pathfinder system (Navigator), and a list of nodes?

But, from your example, I don't see a way to separate the navigator system and the navmesh. If I were to use concurrency, I may have to use static methods to invoke the navigator system to start pathfinding, which would then be required to put the Map object in a tile node. Or I am being mistakened?

At least I now know that it is okay to not put the Map object in each of the tile/path nodes the Map object has contained them in.

#7 DrEvil   Members   -  Reputation: 1105

Like
1Likes
Like

Posted 18 December 2013 - 10:16 AM

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;
    ....
}


#8 ferrous   Members   -  Reputation: 2075

Like
0Likes
Like

Posted 18 December 2013 - 02:52 PM

That's pretty much my setup as well.  I think of the tile nodes on the map as essentially read-only data.  Though I have read about those who try to keep it all in one, and use bit flags so that multiple units can do path searches on the grid.

 

If you're worried about the overhead of the path nodes, you can always have them wrapped up in a memory manager, so it can dole out nodes as needed without constantly allocating and deallocating them during searches.



#9 DrEvil   Members   -  Reputation: 1105

Like
0Likes
Like

Posted 19 December 2013 - 06:55 AM

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.



#10 ferrous   Members   -  Reputation: 2075

Like
0Likes
Like

Posted 19 December 2013 - 01:59 PM

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.

 

Why allocate pools the size of the tilemap?  Depending on the game, I wouldn't imagine most searches would create pathnodes equal to the size of the tilemap.  A simple wrapper like this:

public class ObjectPool<T> where T : class, new()
{
    private Stack<T> m_objectStack = new Stack<T>();

    public T New()
    {
        return (m_objectStack.Count == 0) ? new T() : m_objectStack.Pop();
    }

    public void Store(T t)
    {
        m_objectStack.Push(t);
    }
}

While super simplistic, would do a decent job of keeping allocations to a minimum without the overhead of exponentially increasing the memory footprint.  


Edited by ferrous, 19 December 2013 - 01:59 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS