Diagonal pathfinding

[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!

[Roland_Yonaba]

There is also Jumper. It offers a lot of flexibility, so I guess it might help.

[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

[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.)

[Roland_Yonaba]

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.

[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.