Ideas for advanced platformer pathfinding

M

MishMash

Guest
Hey, I wanted to create this discussion to try and get a primer on ideas for how to best approach pathfinding in an open-world, 2D sandbox platformer. I've hit a bit of a wall with it so far, and am looking for reasonable ideas for how to improve the pathfinding system in general.

To get straight to the point, these are the aims of the system:
- For an NPC to be able to accurately path-find from one location to another. This can include both the following/chasing of another instance, or just moving to a known coordinate location.

- For a pathfinding object to be able to determine if pathing is not possible, or if an existing path has been compromised (as a result of dynamic sandbox interaction, such as placing blocks/destroying blocks). This can be simplified to giving up if a node in the expected path is now obstructed.

- Ability to deal with multiple scenarios within the terrain: Jumping over gaps (given specified size parameters), climbing up ladders, jumping up onto higher ledges, grabbing ledges (This last one is less important, but a stretch goal).

- Ability to path globally across a large world. The player might not see the NPC Travelling, however it would be nice if the player were to move, they might see that NPC in their travels.

- Ability to handle the fact that certain locations might not have been generated at the time and thus disregard paths, unless they are global paths.

- Fast enough that it can be done in real-time for a number of instances simultaneously.
- Paths do not have to be shortest paths, just a reasonable valid path.

I've had a few ideas how to tackle these, however I wanted to get a bit of external opinion from people who may have had experience with similar systems.

Ideas i've had (and tried) so far:

- Split system into "Local" and "Global" paths. Local paths would be the actual node-to-node path that you would see an NPC performing, global paths would be a general mapping from one location to a more distant one in the world. To simplify the overall pathing problem, the NPC would create a local path (which actually follows the terrain) between global path nodes (which could be more arbitrary, such as one node per chunk, or for a point of interest).

- Conventional A* and constructing a grid where each cell is a node and a block seems too slow to do for a world that is constantly changing, so perhaps a scanning algorithm would work better, where each time a path constructed, a grid is generated around that NPC continously testing which regions are validly accessible. (Similar to generating a more localised nodemap, rather than maintaining a world-wide one).

- Global paths would be determined from chunk data rather than pure terrain. (This data-set is far more coarse, and smaller, but not 100% representative of how the world is).

I've attempted a few implementations, the current of which is a crude system where the player generates a path as they walk, the NPC then follows that path. It's okay, but not very robust. I'd love to have the functionality to be able to get an NPC to go anywhere that is feasible for it to go. Having a system like that would make programming certain interactions a dream. (i.e. telling an NPC to walk into a mine, go break some known block and walk back could be a breeze with an advanced pathfinding system).

I appreciate anyone who takes the time to provide suggestions or ideas :)

P.S. If you need any information about the sort of setup i'm working with feel free to ask! Currently the world data is just a grid of block IDs (This is being upgraded to use a custom dll datastructure, however functionally, it'll be the same as a ds_grid, just less memory and faster).
 

Tthecreator

Your Creator!
To get straight to the point, these are the aims of the system:
hehe I see what you did there!

Maybe if you generate a path once, and then instead of regenerating it every step you simply check if anything has changed.
Instead of checking you could also implement it in your game logic maybe? Like whenever you place a block it triggers an event for that specific position.
If you are going to work with dll stuff you might just as well use boolean grids for that.
Doing it this way you could have it O(n). Or if you besides individual grids (per NPC) a global grid O(1) in the best case. (but thinking about it, a global table might not be the best solution since if there is a path being obstructed you'd have extra checks.)
This would take a little bit more memory depending on your room size and can make other things like placing blocks a tiny bit slower. I think this would turn out to be neglectable.
Another problem with this is that whenever a new path opens it can't find the fastest path. But as you stated:
Paths do not have to be shortest paths, just a reasonable valid path.
I hoped this helped somewhat.
I'm of course not as smart as you and I've got less knowledge than you. However, I still gave it a go.

-Tthecreator
 

Simon Gust

Member
I haven't looked into any kind of pathfinding but I believe to know some information that can be of importance.
And tbh, I like to get to know pathfinding.

When finding a path you have to specify the target point, where the instance should end up when it's done.
Say this is an enemy trying to get to the players position. Now, the player is behind several obstacles and walls.
So you could do some pathfinding magic and evaluate the whole path in a grid, global or local.
But, how does the enemy even know the player is there behind x obstacles and y walls?
How does he know the pixel-perfect coordinate position?
Is it reasonable for an enemy, say a cow, to know this kind of stuff?

If I were an enemy, my sense of pathing would be far inferior. So what would I do?
I'd just start walking in a direction I think the player could be, say I heard him from the left.

So I make a path to the left for a bit. OK, I'm there now, let's listen again. Oh, I hear the player in this direction.
let's make a new path and go from there.

/*
And I bet I couldn't remember the layout of the terrain photographically in my head.
This is why we use navi systems, because we don't have those built-in in our brains.
And I doubt enemies in vitality have navi systems.
*/

Soon after I can see the player, but I cannot physically reach him. What do I do now?
Let's walk in this direction, maybe there is a ladder there or something. If there isn't I'm going back and check if the player
is still there, if so, I walk in a different direction, but if that also fails, my journey is over for today. I lose interest.

So this is my non-technical input, I hope it helps.
 
M

MishMash

Guest
Maybe if you generate a path once, and then instead of regenerating it every step you simply check if anything has changed.
Instead of checking you could also implement it in your game logic maybe? Like whenever you place a block it triggers an event for that specific position.
If you are going to work with dll stuff you might just as well use boolean grids for that.
Doing it this way you could have it O(n). Or if you besides individual grids (per NPC) a global grid O(1) in the best case. (but thinking about it, a global table might not be the best solution since if there is a path being obstructed you'd have extra checks.)
This would take a little bit more memory depending on your room size and can make other things like placing blocks a tiny bit slower. I think this would turn out to be neglectable.
Another problem with this is that whenever a new path opens it can't find the fastest path. But as you stated:
Thanks for the input, appreciate it :D! Yeah, defo don't need to re-generate paths unless anything has changed. So assuming were at a point where a path exists, do you think that a path should be invalidated (and re-calculated) when the NPC fails to get to the next node, or do you think it should continuously re-test the full path and verify if still works? (I.e. places where you are supposed to be on the floor, there is a block below and what not).

I created this last night:



It basically works by finding "accessible" regions following a simple set of rules such as jump height restriction. Once a region is marked as accessible, the algorithm is repeated for that new block and then the block is locked in. This is a greedy algorithm, so it doesn't find the most optimal route to a location, just if a route is possible (as once a route is found, it locks in that cell -- for speed reasons).
It seems to find routes for the most part, though given that it doesn't use a cost-based approach, certain routes can get missed out. The good news is that its reasonably fast, 0.25ms to calculate the accessibility grid (Can potentially use ideas from A* to optimise it, as atm it finds ALL accessible places from the current player, when really, it can exit early once the specific path is found, and it could probably use a priority queue to prioritise search in a given direction, rather than just expanding out generally.

Still needs a fair bit of work before it is game ready, but i'm happy that this discussion has helped motivate progress of some sort.

Edit: Managed to improve the algorithm a bit. Better jump and falling paths now:

 
Last edited by a moderator:

John Andrews

Living Enigma
Hi @MishMash , I actually have a WIP that uses this mechanism, it's this one! ,

It's nothing special, just enemies finding you finding the possible path, I'm sorry I couldn't give any help I am not in my code thinking mood rn, just wanted to say I have that project I made some months ago so if you need help you can ask me :D

Well just wanted to share my Idea too :)
 

Simon Gust

Member
Thanks for the input, appreciate it :D! Yeah, defo don't need to re-generate paths unless anything has changed. So assuming were at a point where a path exists, do you think that a path should be invalidated (and re-calculated) when the NPC fails to get to the next node, or do you think it should continuously re-test the full path and verify if still works? (I.e. places where you are supposed to be on the floor, there is a block below and what not).

I created this last night:



It basically works by finding "accessible" regions following a simple set of rules such as jump height restriction. Once a region is marked as accessible, the algorithm is repeated for that new block and then the block is locked in. This is a greedy algorithm, so it doesn't find the most optimal route to a location, just if a route is possible (as once a route is found, it locks in that cell -- for speed reasons).
It seems to find routes for the most part, though given that it doesn't use a cost-based approach, certain routes can get missed out. The good news is that its reasonably fast, 0.25ms to calculate the accessibility grid (Can potentially use ideas from A* to optimise it, as atm it finds ALL accessible places from the current player, when really, it can exit early once the specific path is found, and it could probably use a priority queue to prioritise search in a given direction, rather than just expanding out generally.

Still needs a fair bit of work before it is game ready, but i'm happy that this discussion has helped motivate progress of some sort.

Edit: Managed to improve the algorithm a bit. Better jump and falling paths now:

A thing to think about also is that enteties might not fit 1x1 spaces or similar sizes. You think there is something you can do to not let too narrow paths go through?
Or if you copy the level layout that you kind of scale the grid down that 4x4 spaces in the game world equal 1x1 space in the path-finding world?
 
M

MishMash

Guest
A thing to think about also is that enteties might not fit 1x1 spaces or similar sizes. You think there is something you can do to not let too narrow paths go through?
Or if you copy the level layout that you kind of scale the grid down that 4x4 spaces in the game world equal 1x1 space in the path-finding world?
Yeah atm it doesn't factor in height, was going to just double up the free space checks to include the block above, but scaling down the grid is actually a pretty neat idea, thanks :D
 

Tthecreator

Your Creator!
@MishMash you could scale ot down but if you have a 2 high path, and scale that down, the path might not align correctly with the scaling. So you will need some fancy way of scaling. Like compres 3*3 blocks into ome, but have those 3*3 blocks overlap?
 
M

MishMash

Guest
@MishMash you could scale ot down but if you have a 2 high path, and scale that down, the path might not align correctly with the scaling. So you will need some fancy way of scaling. Like compres 3*3 blocks into ome, but have those 3*3 blocks overlap?
Yeah, that's true D:! Ah well, I'll just do what i planned originally and check n blocks above to verify if the space is free (based on some height parameter).

Edit: Making good progress :D! Managed to get ladders and drop-through platforms working:
 
Last edited by a moderator:

Juju

Member
I did some work for a platformer called Irkalla last year which required many-entity open world navigation with jump-through platforms/slopes etc. I approached the problem from a node-based perspective rather than grid-based.

Since each platform is a continuous navigation space (if you can access the right hand side of a platform, you can access the left hand side) you only need a node at each end of a platform, and where jumps connect from one platform to another. This substantially reduces the complexity of the problem for the pathfinding but not necessarily for the AI as a whole. The system was efficient but required manual placement of nodes which makes it unattractive for the general case (and I never solved the issue of automatically placing nodes, though I reckon it was/is possible).

I'll be keeping tabs on this thread - good luck.
 
Last edited:
M

MishMash

Guest
I did some work for a platformer called Irkalla last year which required many-entity open world navigation with jump-through platforms/slopes etc. I approached the problem from a node-based perspective rather than grid-based.

Since each platform is a continuous navigation space (if you can access the right hand side of a platform, you can access the left hand side) you only need a node at each end of a platform, and where jumps connect from one platform to another. This substantially reduces the complexity of the problem for the pathfinding but not necessarily for the AI as a whole. The system was efficient but required manual placement of nodes which makes it unattractive for the general case (and I never solved the issue of automatically placing nodes, though I reckon it was/is possible).

I'll be keeping tabs on this thread - good luck.
My initial attempt a few months ago tried using nodes, however re-generating the node connections upon a change of the world was quite difficult. Similarly, I was really struggling with calculating things like jump distances (So working out where they could reach with a jump from a given location, the way I was doing it involved scanning, but it was slow). The nice thing about the node method was that once the node map was generated, any instance could use it (whereas my current grid-based system relies on tracking each objects motion and thus requires initial position).

It was also more expensive to "optimise" the node map by collapsing nodes that formed a flat platform, simply because you had to actually check if this was valid. But yeah, I imagine its better once you have the nodes placed, though placing those nodes automatically seemed difficult. It may be something I look into again at some point, though atm, the grid method seems to be proving very successful :D!
 

Simon Gust

Member
So, I've been experimenting with pathfinding for the first time too now. My idea is to do this on the gpu. The code is the same for simple lighting where the player cell has max light and every neighbour cell loses 1 light value and so on.
But instead of light being reduced inside the ground and walls, it is reduced in the air where there is no collision.
upload_2017-10-4_0-10-53.png

Here I've pointed the mouse in the middle of the maze, where a blue pixel is drawn. You can see the blue light reducing towards the entry of the maze.
The objects that use this path should always check the color of the cell their standing on and move towards the higher blue light cells by checking neighbours. That however isn't implemented yet.
I'm amazed I've made it this far because It's midnight by the time I've written this code and post.

The positives about this method should be that all npc share the same path grid and only have to check colors, which is probably inefficient but whatever.
code for the updating (not optimized)
Code:
var step = global.tick mod 16;
if (step == 0)
{
[INDENT]// forbid pathfinding
with (obj_enemy)
{
[INDENT]canFindPath = false;[/INDENT][/INDENT]
}

// reinit surfaces
if (!surface_exists(gridRender)) gridRender = surface_create(128, 128);
if (!surface_exists(pathSurface)) pathSurface = surface_create(128, 128);

// copy main grid collisions to path grid
shader_set(pathObstacleShader);
surface_set_target(gridRender);
draw_clear(0);
texture_set_stage(PFTileSampler, tileTexture);
draw_surface(pathSurface, 0, 0);
surface_reset_target();
shader_reset();
 
// draw target pixel
surface_set_target(gridRender);
var xx = mouse_x/16 - new_gridx;
var yy = mouse_y/16 - new_gridy;
draw_point_colour(xx, yy, c_green);
surface_reset_target();[/INDENT]
}
else
if (step < 9)
{
[INDENT]// update paths
shader_set(pathUpdateShader);
surface_set_target(pathSurface);
repeat (16)
{
[INDENT]draw_surface(gridRender, 0, 0);
surface_copy(gridRender, 0, 0, pathSurface);[/INDENT]
}
surface_reset_target();
shader_reset();[/INDENT]
}
else
if (step == 9)
{
[INDENT]// finish copy
surface_copy(pathSurface, 0, 0, gridRender);
buffer_get_surface(global.pathGrid, pathSurface, 0, 0, 0);

// enable pathfinding
var _x = new_gridx;
var _y = new_gridy;
with (obj_enemy)
{
[INDENT]canFindPath = true;
new_gridx = _x;
new_gridy = _y;[/INDENT]
}[/INDENT]
}
shaders
Code:
/// pathObstacleShader
varying vec2 v_vTexcoord;
varying vec4 v_vColour;
uniform sampler2D tileSampler;

void main()
{
[INDENT]vec4 mid = texture2D(tileSampler, v_vTexcoord);
float red = sign(max(mid.r, mid.g));
gl_FragColor = vec4(red, 0.0, 0.0, 1.0);[/INDENT]
}
and
Code:
/// pathUpdateShader
varying vec2 v_vTexcoord;
varying vec4 v_vColour;
float P = 1.0 / 256.0;

void main()
{
[INDENT]vec4 mid = texture2D(gm_BaseTexture, v_vTexcoord);
if (mid.r < 1.0)
{
[INDENT]if (mid.g > 0.0)
{
[INDENT]gl_FragColor = vec4(0.0, mid.g, 1.0, 1.0);[/INDENT]
}
else
{
[INDENT]vec4 lft = texture2D(gm_BaseTexture, vec2(v_vTexcoord.x - P, v_vTexcoord.y));
vec4 top = texture2D(gm_BaseTexture, vec2(v_vTexcoord.x, v_vTexcoord.y - P));
vec4 rgt = texture2D(gm_BaseTexture, vec2(v_vTexcoord.x + P, v_vTexcoord.y));
vec4 bot = texture2D(gm_BaseTexture, vec2(v_vTexcoord.x, v_vTexcoord.y + P));

float maxA = max(lft.b, top.b);
float maxB = max(rgt.b, bot.b);
float maxC = clamp(max(maxA, maxB) - P, 0.0, 1.0);
gl_FragColor = vec4(0.0, mid.g, maxC, 1.0);[/INDENT]
}[/INDENT]
}
else gl_FragColor = vec4(1.0, 0.0, 0.0, 1.0);[/INDENT]
}
EDIT: optimized a bit and added the enemy move direction concept
NOT TESTED.

Code:
if (canFindPath)
{
[INDENT]/// enemy movement
var xx = x div 16 - new_gridx;
var yy = y div 16 - new_gridy;

// check cells
var offset = 4 * (xx + yy * 128);
var lft = buffer_peek(global.pathGrid, offset - 4, buffer_u8);
var top = buffer_peek(global.pathGrid, offset - 512, buffer_u8);
var rgt = buffer_peek(global.pathGrid, offset + 4, buffer_u8);
var bot = buffer_peek(global.pathGrid, offset + 512, buffer_u8);

hmove = rgt - lft;
vmove = bot - top;[/INDENT]
}
 
Last edited:

RujiK

Member
@Simon Gust Pathfinding on the GPU?! That's crazy cool! I would recommend not using surface_getpixel though, as the manual states:

This function [surface_get_pixel] should not be used very often as it is extremely slow and may cause a pause in your game.
Instead I would try dumping your surface into a buffer via buffer_get_surface() and peek and poke at the data. I think that would be faster.

Also I see that your implementation isn't complete, but have you found any downsides to GPU pathfinding? Have you thought about path finding that takes place off-screen? I would love to ditch CPU pathfinding if GPU based is a viable alternative.
 

Simon Gust

Member
@Simon Gust Pathfinding on the GPU?! That's crazy cool! I would recommend not using surface_getpixel though, as the manual states:
Instead I would try dumping your surface into a buffer via buffer_get_surface() and peek and poke at the data. I think that would be faster.
Also I see that your implementation isn't complete, but have you found any downsides to GPU pathfinding? Have you thought about path finding that takes place off-screen? I would love to ditch CPU pathfinding if GPU based is a viable alternative.
I will test the pathfinding I put across 10 steps of a cycle to see if that works, I wanted to seperate rendering (which also is gpu heavy) too, but that desynct the screen. But pathfinding is a different story, it doesn't have to be accurate as it is not visible. I thought about buffer_get_surface too but I will first test the speed difference.
The main performance killer however is the surface_copy that is supposedly running 256 times a step, it may be only a 128x128 surface but still.
I cannot extend pathfinding beyond rendering (2048x2048 pixels) as I copy contents of the tile rendering to the pathfinding surface. So I just thought of "go towards the rendering area" as an enemy.
 

Simon Gust

Member
@Simon Gust Pathfinding on the GPU?! That's crazy cool! I would recommend not using surface_getpixel though, as the manual states:



Instead I would try dumping your surface into a buffer via buffer_get_surface() and peek and poke at the data. I think that would be faster.

Also I see that your implementation isn't complete, but have you found any downsides to GPU pathfinding? Have you thought about path finding that takes place off-screen? I would love to ditch CPU pathfinding if GPU based is a viable alternative.
Reply 2:
I managed to get it working correctly, but just as you suggested. surface_getpixel is a killer. I have one pathfinder object and the red bar goes from short to half.
I will have to do the buffer method.

EDIT: Buffer seems fast. Was a hassle though, buffer get surface's format is weird and it loads the surface like this
Code:
for (y)
{
 for (x)
 {
 
 }
}
which is undesireable but I fortunately knew about it beforehand.
//////////////
Since it doesn't update every step, the npcs might clip the wall if I use it as a path. I have to use it more like a node system.
A downside to this gpu pathfinding is of course that the max range is only 255 cells before npcs give up alltogether. And those 255 cells aren't a linear distance.[/code]
 
Last edited:

Simon Gust

Member
It is a LOT faster if the surface isn't currently in the render pipeline. Try using two surfaces and update them alternately, checking the pixel value of the surface that is NOT being updated that frame. :)
The surface / buffer checking only happens on non update frames (frame 9 to 15) using canFindPath as a variable.
It does reduce peformance cost a bit though when I don't draw the surface for visuals, but using buffers is still a lot better.
 
M

MishMash

Guest
It is a LOT faster if the surface isn't currently in the render pipeline. Try using two surfaces and update them alternately, checking the pixel value of the surface that is NOT being updated that frame. :)
Don't mean to necro bump, only just saw this potential nugget! So, I have a few problems with my water simulation at the moment in that checking it is rather slow (so we only pull values from it 3 times a second). Conveniently, there is a temp swap-out surface, and their use is alternated each frame, are you saying if I pulled that frame-old data instead, it should be faster? I was under the impression that both surfaces were stored on the GPU anyway, so regardless of which one is fetched, surely it would still take the same amount of time to transfer that data from the GPU?

Similarly, I believe I may be doing this the moment before it gets updated (which may already be the alternative frame?) given that the buffer_get_surface happens in the Step event just before draw runs, does the event locality have an impact?

------- To avoid making this too off-topic -------
I ended up having a lot of success with this pathfinding system, realising it could also be used to solve arbitrary search problems by just changing the heuristic check. For example, as it is an expansive accessible-location search algorithm, so if I wanted to find a location near water, rather than having to pre-scan for a location, then plug it in to path to, it's immediately equally efficient as just finding that path, even if the destination is known, by changing the success condition from "are we at the destination in this cell?" to "Is this cell in water?" I could instantly get an entity to navigate to water:


(In this case, it checks if the water is atleast 2 blocks deep)
Link to a post I wrote about it on GameJolt: https://gamejolt.com/games/vitality/171430/devlog/pathfinding-system-epic-upgrade-m7ivxkef
 
Top