I'm programming a simple tile-based puzzle game, and I've gotten stuck trying to work out a pathfinding algorithm.
Here's how the game is set out:
- The game board is (arbitrarily) 8 tiles wide by 8 tiles tall.
- Each tile can be one of four types (shown below as red, green, blue and yellow)
- Additionally, a tile could be a reactor (the starting point of a path - this will become clear later on)
The board would look something like this:
(The reactors are the circles; the other tiles have no special properties.)
What I need to do is: starting from a reactor, trace the longest path along adjoining tiles of the same color as the reactor. Something like this:
The blue reactor is simple(ish) as its path doesn't branch. However, as you can see from the green reactor's start position, its path can branch two ways at the start (up or down), and take a detour midway through.
The path I'm looking for is the longest one, so that's the one that's highlighted in the screengrab (the first path only crosses two tiles, and the detour midway results in a sorter path).
When certain conditions have been fulfilled, the reactor will cause all the tiles in the longest path (where the arrows cross in the diagram) to disappear and be replaced with new ones. All other tiles will remain in place, including the extraneous green tiles adjacent to the green reactor's path.
I'm guessing something like a modified flood fill would work, but I'm not really sure how to start.
If it makes any difference, I'm using Swift to write the game.
The tiles are stored in an approximation of a 2D array (Swift doesn't have a robust native implementation of that yet, so I'm using the one described in this tutorial). They're retrieved using tile[column, row]
.
----------EDIT 2/12/2016----------
With some help from a friend, I've written a recursive function that should return the longest path. It's looping through correctly, but it's not pruning shorter branches from the longestPath
array.
Can anyone see where I'm going wrong in this code?
Here's the recursive function:
func pathfinder(startingTile: Tile, pathToThisPoint: Chain, var iteration: Int? = 1) -> Chain
{
var longestPath: Chain? = nil
var availableTiles = getNeighbouringTiles(startingTile)
for var nextTile = 0; nextTile < availableTiles.count; nextTile++
{
let column = availableTiles[nextTile].column
let row = availableTiles[nextTile].row
if tiles[column, row]!.tileType == startingTile.tileType && (tiles[column, row]!.isReactor == false || startingTile.isReactor)
{
// if we haven't been here before
if !pathToThisPoint.tiles.contains(tiles[column, row]!)
{
print(iteration)
iteration = iteration! + 1
// add this tile to the pathtothispoint
// go to the next unexplored tile (recurse this function)
pathToThisPoint.tiles.append(tiles[column, row]!)
let tempPath = pathfinder(tiles[column, row]!, pathToThisPoint: pathToThisPoint)
// if the resulting path is longer...
if tempPath.tiles.count > longestPath?.tiles.count
{
// then tempPath is now the longest path
longestPath = tempPath
}
}
}
if longestPath != nil
{
return longestPath!
}
else
{
return pathToThisPoint
}
}
It's dependent on the getNeighboringTiles function (shown below) that returns an array of valid tiles of the same type, excluding reactors:
func getNeighbouringTiles(tile: Tile, previousTile: Tile? = nil) -> Array<Tile>
{
var validNeighbouringTiles = Array<Tile>()
var neighbourTile: Tile
// check top, right, bottom, left
if tile.row < NumRows - 1
{
neighbourTile = tiles[tile.column, tile.row + 1]!
if neighbourTile.tileType == tile.tileType && !neighbourTile.isReactor && (previousTile == nil || previousTile != neighbourTile)
{
validNeighbouringTiles.append(neighbourTile)
}
}
if tile.column < NumColumns - 1
{
neighbourTile = tiles[tile.column + 1, tile.row]!
if neighbourTile.tileType == tile.tileType && !neighbourTile.isReactor && (previousTile == nil || previousTile != neighbourTile)
{
validNeighbouringTiles.append(neighbourTile)
}
}
if tile.row > 0
{
neighbourTile = tiles[tile.column, tile.row - 1]!
if neighbourTile.tileType == tile.tileType && !neighbourTile.isReactor && (previousTile == nil || previousTile != neighbourTile)
{
validNeighbouringTiles.append(neighbourTile)
}
}
if tile.column > 0
{
neighbourTile = tiles[tile.column - 1, tile.row]!
if neighbourTile.tileType == tile.tileType && !neighbourTile.isReactor && (previousTile == nil || previousTile != neighbourTile)
{
validNeighbouringTiles.append(neighbourTile)
}
}
// if we get this far, they have no neighbour
return validNeighbouringTiles
}
The Tile class looks like this (methods omitted for brevity):
class Tile: CustomStringConvertible, Hashable
{
var column:Int
var row:Int
var tileType: TileType // enum, 1 - 4, mapping to colors
var isReactor: Bool = false
// if the tile is a reactor, we can store is longest available path here
var reactorPath: Chain! = Chain()
}
And finally, the chain class looks like this (again, methods omitted for brevity):
class Chain {
// The tiles that are part of this chain.
var tiles = [Tile]()
func addTile(tile: Tile) {
tiles.append(tile)
}
func firstTile() -> Tile {
return tiles[0]
}
func lastTile() -> Tile {
return tiles[tiles.count - 1]
}
var length: Int {
return tiles.count
}
}