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?
Pathfinding in a chunked world
Forum rules
Before you make a thread asking for help, read this.
Before you make a thread asking for help, read this.
-
- Party member
- Posts: 234
- Joined: Mon Aug 29, 2016 8:51 am
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.
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.
-
- Party member
- Posts: 234
- 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.
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.
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.
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.
-
- Party member
- Posts: 234
- 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.
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.
-
- 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
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
-
- 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:
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
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
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.
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.
-
- 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
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
-
- 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
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: Bing [Bot] and 9 guests