Author Topic: grid based pathfinding help  (Read 3291 times)

i suck at math but i need to design this system. its for a strategy game. its crucial.

the map itself and all its tiles is being generated from the ground up, which means that there will be no manual nodemapping, all this has to be generated automatically with the map based on the data provided (coordinates, tile type, etc)



i'm good at understanding explanations on how code should work in theory. that's mainly what i want here, i just need someone to tell me how this system will work in theory. i don't need psuedocode or anything, just like "you should check the direction and do blah"

since A* branches out, you could just put the check there

ie

123
456
789

starting at 5, check if it's a ramp
if it's  N ramp, it checks 2 on curLevel+1 and checks 8 on curLevel
and so on for E/S/W ramps

if it's not a ramp
check 2/4/6/8 on curLevel
if they're ramps facing the wrong way, skip over them


it would help to know how you're laying out the tiles and what data structures you're using
if it's a static grid, it may be easier to just use arrays
if it's not, you could probably still use arrays since torque is weird like that

alright that makes sense thanks

also, instead of just straight out ignoring those paths, you can give them a higher weight
that way if they can scale a wall, they will do it if it's faster than walking around the wall

When I was working on this in relation to a board game-esque thing i was tinkering on, I adapted Slayer's A* implementation. How it works is that you create nodes and create links between them. Then when you ask for a path, it checks links from node to node as valid paths between them and calculates the optimal route.

Since it was quite a task to comprehend that entire system, if you want I can maybe dust off that old project and explain how the different parts work with examples.

The nodes in this case are just the tiles. Maybe some people are used to thinking of them as just points, but the tiles are just an area that represents a very large point of walk-ability. Same principle with voxels for atoms/molecules/simulated particles...

What's important about height and obstacles is recording what neighbors are 'visible' for each node. So on a completely flat plane, each node will have four legitimate neighbors since there's no obstacles for walking to another node. It might help to think of the higher tiles as the lower tiles but surrounded by thin walls, and the ramp would be the open part of the wall. What a path finding algorithm would do (in the case of A*) is similar to a flood fill in paint, but the "next pixels we fill per tick" is determined by a heuristic function (distance usually). If the walk-able tiles are white pixels and the walls are black in that case, then the flood fill will wrap around the wall and eventually find the destination. It may not be efficient because the distance to a higher tile can just be one tile over realistically, but instead the algorithm will "blob up" and when the edge of the blob reaches the ramp it will snipe the destination.

So the important thing to do is keep track of a tile's neighbor's accessibility when you generate them. Since you're using a 2D system, just check the four neighbors of a tile when you generate it and compare z values to determine visibility, as a starting point. From the perspective of a regular tile, a ramp could be treated as accessible for a range of z values depending on its rotation. This means for each type of walk-able tile defined in the game, it needs a visibility determination function for every other type including itself, so maybe define this abstractly in a nice virtual function. Don't forget to update the already existing neighbors too, each tile has to consider its four neighbors and if one doesn't exist but will exist soon then it needs an update when its actually created.

as for data structures and data representation, i'd use a bitmask for which way the paths are open

Code: [Select]
$paths[north] = 1;
$paths[east] = 2;
$paths[south] = 4;
$paths[west] = 8;

and $paths[%x, %y, %z] for setting/looking at paths

this way you can quickly do if($paths[%x, %y, %z] & $paths[south]) to check if a path can be accessed from the south

whats the significance of 1 2 4 8

Those are bit numbers. Bit numbers are usually in 2^x

yeah but whats the significance of doing that? is it at all practical

yeah but whats the significance of doing that? is it at all practical
faster to do bitwise comparasions than value comparisons, and you can have values that would pass more than one value check

ex: the value of 6 would mean you can go east and south

for now i'm just gunna store neighbors as a variable on the node itself.



the red lines and green cubes are mostly for debug, once i figure out how to load ramps in i'll use that

Ramps are considered 'cubes' when you do raycasting checks (if that's what you are doing unless you are manually doing this) - so it's a bit challenging.. I have tried this before.

I never knew you could use bitmasks to do something neat like this, I wish I knew that sooner.

yeah but whats the significance of doing that? is it at all practical
well that's what bitmasks are for
you set certain bits in a number on or off to represent an answer to a single yes/no question
like the first bit could be "is there an open pathway to the north of this node"
2nd could be "is there an open pathway east of this node"
then south and west.
Then, to check if there's an open pathway to the east, you'd do (%bitmask & $paths[east]) != 0 to see if there is a path open to the east.
The & operator is what "masks" the bit, checking to see if that one bit and that one bit alone is set to 1 or 0.

Ramps are considered 'cubes' when you do raycasting checks (if that's what you are doing unless you are manually doing this) - so it's a bit challenging.. I have tried this before.

I never knew you could use bitmasks to do something neat like this, I wish I knew that sooner.
raycasts are dumb for this. when i load the map up, i just assign numbers to a 3d array and access that when i need to check if a space is occupied or where you can move, etc. ramps use numbers 2-5 for direction and stuff, and when the player moves onto it they just stand in the center i guess