Diagonal pathfinding

[CanadianGamer]

Hey guys is there any way to use an existing pathfinding library to accept diagonal connections?
I'm asking because I'm making a board game where the goal is to make a connection from one of
your bases to another before your opponent does.

[marco.lizza]

I'm not using any 3rd party library, but in my pathfinding module this is a simple matter of considering diagonal steps a valid "neighbour" move.

Are you using any specific library?

[CanadianGamer]

I haven't chosen one yet simply because I haven't found one that can do diagonal pathfinding that I can see

[marco.lizza]

To be honest, implementing a simple (unoptimized) Dijkstra's pathfinding algorithm is quite simple.

The most difficult thing is handling the representation of the map in a graph-oriented way.

How is your game "world" represented? Could you be more specific and give some details about?

[CanadianGamer]

here is an example

I'm trying to use the pathfinding libraries to see if a player has won

in this case red has won

[marco.lizza]

I'm trying to use the pathfinding libraries to see if a player has won

Which is the criteria to determine if a player has won? Despite being a possible approach, I don't think that pathfinding is the most convenient tool to use for this problems. You should simply scan the board and check if some predefined "patterns" are present.

[pgimeno]

Doing a floodfill of the player's cells from the starting point to see if the ending point is touched, would suffice. According to your description, it seems you need a floodfill algorithm that can also step diagonally.

A simple but somewhat costly floodfill algorithm is (in pseudocode):

Code: Select all

function floodfill(x, y)
  if x == target x and y == target y then
    return true
  end
  mark cell[x, y] as visited
  -- fill adjacent
  if cell[x-1, y] belongs to the player and is not visited then
    if floodfill(x-1, y) then return true end
  end
  if cell[x+1, y] belongs to the player and is not visited then
    if floodfill(x+1, y) then return true end
  end
  if cell[x, y-1] belongs to the player and is not visited then
    if floodfill(x, y-1) then return true end
  end
  if cell[x, y+1] belongs to the player and is not visited then
    if floodfill(x, y+1) then return true end
  end
  -- fill diagonals
  if cell[x-1, y-1] belongs to the player and is not visited then
    if floodfill(x-1, y-1) then return true end
  end
  if cell[x-1, y+1] belongs to the player and is not visited then
    if floodfill(x-1, y+1) then return true end
  end
  if cell[x+1, y-1] belongs to the player and is not visited then
    if floodfill(x+1, y-1) then return true end
  end
  if cell[x+1, y+1] belongs to the player and is not visited then
    if floodfill(x+1, y+1) then return true end
  end
end

function player_won(start cell's x, start cell's y)
  mark all cells as not visited
  return floodfill(start cell's x, start cell's y)
end

In the worst case, this function can recurse up to as many levels as there are player cells. There are other less costly but more complicated flood fill algorithms. I'm not sure how many of them are suitable to be converted to be able to travel diagonally.

[marco.lizza]

Doing a floodfill of the player's cells from the starting point to see if the ending point is touched

I also thought about flood-filling the grid... but, quite frankly, I still don't get the game mechanics.

[CanadianGamer]

Doing a floodfill of the player's cells from the starting point to see if the ending point is touched, would suffice. According to your description, it seems you need a floodfill algorithm that can also step diagonally.

A simple but somewhat costly floodfill algorithm is (in pseudocode):

Code: Select all

function floodfill(x, y)
  if x == target x and y == target y then
    return true
  end
  mark cell[x, y] as visited
  -- fill adjacent
  if cell[x-1, y] belongs to the player and is not visited then
    if floodfill(x-1, y) then return true end
  end
  if cell[x+1, y] belongs to the player and is not visited then
    if floodfill(x+1, y) then return true end
  end
  if cell[x, y-1] belongs to the player and is not visited then
    if floodfill(x, y-1) then return true end
  end
  if cell[x, y+1] belongs to the player and is not visited then
    if floodfill(x, y+1) then return true end
  end
  -- fill diagonals
  if cell[x-1, y-1] belongs to the player and is not visited then
    if floodfill(x-1, y-1) then return true end
  end
  if cell[x-1, y+1] belongs to the player and is not visited then
    if floodfill(x-1, y+1) then return true end
  end
  if cell[x+1, y-1] belongs to the player and is not visited then
    if floodfill(x+1, y-1) then return true end
  end
  if cell[x+1, y+1] belongs to the player and is not visited then
    if floodfill(x+1, y+1) then return true end
  end
end

function player_won(start cell's x, start cell's y)
  mark all cells as not visited
  return floodfill(start cell's x, start cell's y)
end

In the worst case, this function can recurse up to as many levels as there are player cells. There are other less costly but more complicated flood fill algorithms. I'm not sure how many of them are suitable to be converted to be able to travel diagonally.

thanks

[CanadianGamer]

Doing a floodfill of the player's cells from the starting point to see if the ending point is touched

I also thought about flood-filling the grid... but, quite frankly, I still don't get the game mechanics.

Basically the players take turns putting down connector pieces (the ones without stroke) to connect they're bases (the ones with stroke)