Page 2 of 2
Re: Diagonal pathfinding
Posted: Sun Jun 19, 2016 4:35 am
by DanielPower
Perhaps this will be useful to you. It's a pathfinding library I wrote a few weeks back for a project I'm working on. It uses the astar algorithm and does support diagonals.
https://github.com/DanielPower/zStar
Code: Select all
zArray = require('zArray')
zStar = require('zStar')
red.start = {x=5, y=1}
red.finish = {x=1, y=5}
red.collidables = {}
-- Set all nodes as collidable
for x=1, grid.width do
for y=1, grid.height do
zArray.set( red.collidables, x, y, true )
end
end
function red.placePiece(x, y)
zArray.set( red.collidables, x, y, false )
if zStar.getPath( red.start.x, red.start.y, red.finish.x, red.finish.y ) ~= nil then
red.victory()
end
end
Do the same thing for blue. If efficiency matters to you (which for this type of game, it probably doesn't), one optimization would be to modify my library to move along collidable nodes, instead of non-collidable nodes. This would allow you to avoid setting every node to collidable at the beginning of every game. It's almost negligible unless you're using massive grids, so I wouldn't worry about that.
Let me know if you have any issues, I'll be happy to help!
Re: Diagonal pathfinding
Posted: Sun Jun 19, 2016 3:02 pm
by Roland_Yonaba
There is also
Jumper. It offers a lot of flexibility, so I guess it might help.
Re: Diagonal pathfinding
Posted: Sun Jun 19, 2016 3:40 pm
by Skeletonxf
@DanielPower Couldn't you just swap the logic around instead of changing the library?
Code: Select all
zArray = require('zArray')
zStar = require('zStar')
red.start = {x=5, y=1}
red.finish = {x=1, y=5}
red.collidables = {}
-- don't set all nodes as collidable
--for x=1, grid.width do
-- for y=1, grid.height do
-- zArray.set( red.collidables, x, y, true )
-- end
--end
function red.placePiece(x, y)
zArray.set( red.collidables, x, y, true)
if not zStar.getPath( red.start.x, red.start.y, red.finish.x, red.finish.y ) then
red.victory()
end
end
Re: Diagonal pathfinding
Posted: Sun Jun 19, 2016 5:44 pm
by DanielPower
No, that wouldn't work because the pathfinding algorithm would look around the red pieces. So as long as there is a path of white space between the start and finish, the game cannot be won.
Example:
Code: Select all
[B][0][0][0][R]
[0][b][0][0][0]
[0][0][b][0][0]
[r][r][0][b][0]
[R][r][0][0][B]
This would cause a victory for red, because it would cause there to be no possible path between R and R. Even though there isn't a complete line between R and R.
Also, this would not cause a victory for blue, because even though there is a complete line from B to B, the pathfinder can still follow the empty spaces around it, and complete a path.
The working solution would be to consider all blank spaces as collidable, and then consider each placed piece to be non-collidable.
This case also makes me think I should make a modification to my zStar library so it takes the collidables table as an argument, rather than storing it in the library. Because in this case, red and blue would each have their own separate collidables tables.
EDIT: @Roland_Yonaba thanks for linking to Jumper. I was looking for a pathfinding library before I wrote zStar, but couldn't find one that met my needs. If I had found Jumper, I may not have written zStar. (Assuming it runs as fast as zStar that is.)
Re: Diagonal pathfinding
Posted: Sun Jun 19, 2016 10:54 pm
by Roland_Yonaba
DanielPower wrote:
EDIT: @Roland_Yonaba thanks for linking to Jumper. I was looking for a pathfinding library before I wrote zStar, but couldn't find one that met my needs. If I had found Jumper, I may not have written zStar. (Assuming it runs as fast as zStar that is.)
Feel free to run some tests. Also, note that Jumper provides lots of pathfinding algorithms.
Jump Point Search (direct pdf link) might sound interesting to you.
Re: Diagonal pathfinding
Posted: Mon Jun 20, 2016 12:42 am
by DanielPower
That was an awesome read! The only issue I have however, is I don't think Jump Point Search can incorporate G costs for different tiles? Please correct me if I'm wrong about this. One of the features I need for my game (though I haven't added it to zStar yet, I will soon), is to have tiles with different G costs.
I will definitely look more into Jumper though, and I'll consider JPS for projects that don't require variable G costs.