Pathfinding in a chunked world

[KayleMaster]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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