## Pathfinding in a chunked world

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
KayleMaster
Party member
Posts: 223
Joined: Mon Aug 29, 2016 8:51 am

### Pathfinding in a chunked world

How would I do this?

I have chunks with a 64x64 grid and when a unit needs to move from his location to gx,gy (global position x,y - transformable to chunk coordinates) he may need to pass through multiple chunks.

However, I don't have a global collision map and each chunk has it's own. But the pathfinder needs only 1.

Sooo, would I assemble dynamically a global collision map from the discovered chunks ,which may be very large and kinda ruins the point of chunking, or use some kind of HPA* which is beyond my IQ unfortunately.

I don't need a perfect pathfinder, even a greedy one will do, so fire away any ideas that you may have.

EDIT: may be I could rework the pathfinder to just pull of data straight from my chunks?

erasio
Party member
Posts: 118
Joined: Wed Mar 15, 2017 8:52 am
Location: Germany

### Re: Pathfinding in a chunked world

Tbh. HPA* is the easiest solution. Or rather any form of hierarchical Pathfinding.

If you're fine with some gameplay / chunk restrictions it should be fairly simple to implement (aka an edge is either fully traversable or fully blocked. That makes the whole problem a lot easier as you can just work with chunks like you would with a tile.

KayleMaster
Party member
Posts: 223
Joined: Mon Aug 29, 2016 8:51 am

### Re: Pathfinding in a chunked world

I don't think I can generate the graphs needed for HPA*, considering my chunks are 64x64.
That means 64 nodes per side of chunk (4 sides) each doing pathfinding to every other node on the side in the chunk to generate a graph.
Any ideas?
Maybe I should split my chunks even more, to like 8x8. Also I saw a comment, about not using A* but floodfill to generate the graph, I'm still not sure how that works.

erasio
Party member
Posts: 118
Joined: Wed Mar 15, 2017 8:52 am
Location: Germany

### Re: Pathfinding in a chunked world

As I said. You can drastically reduce the amount of nodes by restricting yourself in certain ways.

For example only allowing chunk edges (aka left side) to only be traversable or not.

Don't force yourself to use a very specific implementation.

The basic idea of hierarchical pathfinding is to abstract larger areas in chunks, precomputing possible connections and distances from possible entry to exit points.

Those do not need to represent all possible entry and exit points. Only enough for your ai to do what it should do.

Exact pathfinding is only necessary in your immediate surrounding.

That's why you use hierarchical pathfinding in the first place. You sacrifice some precision and use some estimations to make it work seamlessly in huge areas. In static environments this can be fairly precise... at the cost of ram.

You can try to generate 256 nodes per chunk. If you don't store a ton of data in them, you ain't wasting a lot of ram. I've coded Pathfinding in the past with a few bytes per node. Having thousands of them at a time (which used less than 10mb ram total).

If it becomes too much you have to scale down precision. You can detect where a transition between chunks is and then detect the middle of that. You don't sacrifice much data but reduce the data needed to just one node per opening. And the imprecision introduced only means you are more likely to overestimate the path cost (or have your ai primarily move towards the middle of opening).
Plus runtime speed is increased by quite a bit because you don't have to find the faster node. There's always an immediately obviously fastest way since each entry and exit has just one node.

If your environment is generated this obviously gets a lot harder.

KayleMaster
Party member
Posts: 223
Joined: Mon Aug 29, 2016 8:51 am

### Re: Pathfinding in a chunked world

My world is currently generated and that's why I'm worried about the graph build speed. I mau try to parralelize it but I'll have to serialize the chunk..

I'm gonna stick with a global collision map for now and put HPA* on backburner.
I don't think my world will be randomly generated later, but have premade worlds, so I can process the graph in advance.

DarkShroom
Citizen
Posts: 86
Joined: Mon Jul 17, 2017 2:07 pm

### Re: Pathfinding in a chunked world

i dunno if this is relevant to you but i am currently implementing YET AGAIN the same old pathfinding i always use (i never tend to use A*)

you just basically implement a floodfill, but counting up the numbers as you go... you check for empty squares on one map, and count up the count as you go

block map:
0 0 1 0
0 0 0 0
0 1 1 0
0 0 1 0

floodfill map:

11 12 0 16
12 13 14 15
13 0 0 16
14 15 0 17

if your floodfill ever reaches the target you just count backwards along the numbers, you can also cancel the floodfill in case you reach the destination

DarkShroom
Citizen
Posts: 86
Joined: Mon Jul 17, 2017 2:07 pm

### Re: Pathfinding in a chunked world

i am dumping it in my github more tidy later, currently no limits to search range etc, other things to refactor like i will bypass checking if start or destination is blocked etc

however, i find this robust and i like it uncomplicated while in love 2d, it's good for my purposes already, it's best not to go too crazy with pathfinding i find and focus on it's implementation and usage

i don't even know if this is what you meant in your question, but just in-case:

Code: Select all

function pathfind(map, x2, y2, x1, y1)

map_width = #map[1]
map_height = #map

local function in_bounds(x, y) --check location is in bounds of map
return x > 0 and
y > 0 and
x <= map_width and
y <= map_height
end

local translations = { --valid move directions, note we do not have diagonal translations
{0, 1},
{1, 0},
{0, -1},
{-1, 0}
}

path_map = {} --generate a new map of 0s that has the same dimensions
for y, row in ipairs (map) do
local new_row = {}
for x, val in ipairs(row) do
table.insert(new_row, 0)
end
table.insert(path_map, new_row)
end

local fill_positions = {{x1,y1,9}} -- startx, starty, currentvalue .. this is a list of positions to check next

local sucess = false

while #fill_positions > 0 do

local current_pos = table.remove(fill_positions,1) --lua "pop" the first element in a table

local xPos = current_pos[1]
local yPos = current_pos[2]
local count = current_pos[3]

if in_bounds(xPos, yPos) then
if map[yPos][xPos] == 0 and path_map[yPos][xPos] == 0 then --both squares on maps are free
path_map [yPos][xPos] = count + 1 --mark with count + 1

if xPos == x2 and yPos == y2 then
sucess = true
break --if we reach destination we can cancel flood fill
end

for _,translation in ipairs(translations) do --add all the surrounding squares to a check list
-- print(inspect(translation))
local new_fill_pos = {xPos + translation[1], yPos + translation[2], count +1}
table.insert(fill_positions, new_fill_pos)
end
end
end
end

local results = {}

if sucess then

local current_pos = {x2,y2}

table.insert (results, current_pos)

while true do
local current_number = path_map[current_pos[2]][current_pos[1]]
if current_number == 10 then --we must have reached the destination (value 10)
break --so break loop
end

for _, translation in ipairs(translations) do --look for first tile surrounding with a number one lower
local check_pos = {current_pos[1]+translation[1], current_pos[2] + translation[2]}
if in_bounds(check_pos[1], check_pos[2]) then
if path_map[check_pos[2]][check_pos[1]] == current_number - 1 then

table.insert(results, check_pos) --save the result
current_number = current_number - 1 --lower the current number
current_pos = check_pos
break --don't check any more translations as this one was okay (loop will continue)
end
end
end
end
return results
end
end

local test_map = {
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 1, 1, 0},
{0, 0, 1, 0},
}

print('PATHFIND TESTS')
print('pathfind result:',inspect(pathfind(test_map, 1,1, 4,4)))
print('pathfind result:',inspect(pathfind(test_map, 1,1, 3,4))) --blocked example


if i get more advanced, i tend to separate out the fill bit and the go backwards along path bit... you can set it up so we have a sort of predicate input, to ask questions like... find the nearest apple etc

erasio
Party member
Posts: 118
Joined: Wed Mar 15, 2017 8:52 am
Location: Germany

### Re: Pathfinding in a chunked world

Be careful with on the fly flood filling.

There's a reason A* is the standard... Or actually it isn't really anymore. Not for all use cases anyway. We do have jps too now (jump point search, a highly optimized A*).

Anyway. Point being. Flood fill is a lot slower as it needs a lot more iterations to find any destination.

It can be helpful to not only have the shortest path but also the other info. But unless you intent to use it I wouldn't advise it. Any performance concerns will just get worse and a pure A* without clusters will be very significantly faster.

DarkShroom
Citizen
Posts: 86
Joined: Mon Jul 17, 2017 2:07 pm

### Re: Pathfinding in a chunked world

actually flood fill can be faster, especially for say a map with lots of dead ends

further it can be faster if you have a waypoint, because you can share the floodfill with other units

in my usages cases A* is barely worth it, i want to move on to actual gameplay now

DarkShroom
Citizen
Posts: 86
Joined: Mon Jul 17, 2017 2:07 pm

### Re: Pathfinding in a chunked world

another thing you can't do with A* is ask for the nearest apple

this is very important to me personally, for my AI might want to find like the nearest item, and it just could be a can of worms if i need to weight a direction for that

but yeah i might add A* if people actually used my framework, like as an option, or if i had a specific usage scenario i thought i could get more performance out of it

### Who is online

Users browsing this forum: No registered users and 29 guests