Recursive Pathfinding in Swift - find longest path

Question

(Sorry for the cross-post, but I put this up on GameDev.Stackexchange and it's not getting much traffic, so I thought I'd try here as well.)

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.

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

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 (for example, the longest path would include the 2-tile branch below the reactor, as well as the single-tile detour at the top of the arch).

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)
                pathToThisPointaddTile(tiles[column, row]!)

                let tempPath = pathfinder(tiles[column, row]!, pathToThisPoint: pathToThisPoint)



                // if the resulting path is longer...
                if tempPath.length > longestPath.length
                {
                    // then tempPath is now the longest path
                    for var i:Int = 0; i < tempPath.length; i++
                    {
                        let tile = Tile(column: pathToThisPoint.tiles[i].column, row: pathToThisPoint.tiles[i].row, tileType: pathToThisPoint.tiles[i].tileType)
                        longestPath?.addTile(tile)
                    }

                }
            }
        }

        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
    }
}

----------------------- EDIT : REPLACEMENT PATHFINDER ------------------------

I've attempted to convert User2464424's code to Swift. Here's what I've got:

func calculatePathsFromReactor(reactor: Tile) -> Chain?
{
    func countDirections(neighbours: [Bool]) -> Int
    {
        var count: Int = 0
        for var i:Int = 0; i < neighbours.count; i++
        {
            if neighbours[i] == true
            {
                count++
            }
        }
        return count
    }

    var longestChain: Chain? = nil
    longestChain = Chain()
    var temp: Chain = Chain()
    var lastBranch: Tile = reactor
    var lastMove: Int? = reactor.neighbours.indexOf(true)




    func looper(var currentTile: Tile)
    {
        if currentTile != reactor
        {
            if countDirections(currentTile.neighbours) > 2 //is branch
            {
                lastBranch = currentTile
            }
            if countDirections(currentTile.neighbours) == 1 //is endpoint
            {
                lastBranch.neighbours[lastMove!] = false // block move out of the last branch found

                if longestChain.length < temp.length
                {
                    longestChain = temp
                }
                currentTile = reactor // return to reactor and redo
                lastVisitedTile = reactor
                temp = Chain() //reset to empty array
                lastBranch = reactor
                lastMove = reactor.neighbours.indexOf(true)
                looper(currentTile)
            }
        }

        //let tempTile: Tile = Tile(column: currentTile.column, row: currentTile.row, tileType: currentTile.tileType, isReactor: currentTile.isReactor, movesRemaining: currentTile.movesRemaining)
        //tempTile.neighbours = currentTile.neighbours

        if currentTile.neighbours[0] == true
        {
            if !temp.tiles.contains(currentTile)
            {
                temp.addTile(currentTile)
            }
            if countDirections(currentTile.neighbours) > 2
            {
                lastMove = 0
            }
            lastVisitedTile = currentTile
            currentTile = tiles[currentTile.column, currentTile.row + 1]! //must avoid going backwards
            if !temp.tiles.contains(currentTile)
            {
                looper(currentTile)
            }
        }

        if currentTile.neighbours[1] == true
        {
            if !temp.tiles.contains(currentTile)
            {
                temp.addTile(currentTile)
            }
            if countDirections(currentTile.neighbours) > 2
            {
                lastMove = 1
            }
            lastVisitedTile = currentTile
            currentTile = tiles[currentTile.column + 1, currentTile.row]! //must avoid going backwards
            if !temp.tiles.contains(currentTile)
            {
                looper(currentTile)
            }
        }

        if currentTile.neighbours[2] == true
        {
            if !temp.tiles.contains(currentTile)
            {
                temp.addTile(currentTile)
            }
            if countDirections(currentTile.neighbours) > 2
            {
                lastMove = 2

            }
            lastVisitedTile = currentTile
            currentTile = tiles[currentTile.column, currentTile.row - 1]! //must avoid going backwards
            if !temp.tiles.contains(currentTile)
            {
                looper(currentTile)
            }
        }

        if currentTile.neighbours[3] == true
        {
            if !temp.tiles.contains(currentTile)
            {
                temp.addTile(currentTile)
            }
            if countDirections(currentTile.neighbours) > 2
            {
                lastMove = 3
            }
            lastVisitedTile = currentTile
            currentTile = tiles[currentTile.column - 1, currentTile.row]! //must avoid going backwards
            if !temp.tiles.contains(currentTile)
            {
                looper(currentTile)
            }
        }
    }




    // trigger the function for the reactor tile
    looper(reactor)

    return longestChain
}

(The neighbours property is a struct containing four named variables: above, right, below and left, each initialised to false and then set to true by a function that runs immediately before the pathfinder.)

I'm finding a couple of issues now. The code loops as it should, but stops at the top of the arch, under the single-tile detour - the path that's returned is only 4 tiles long (including the reactor).

The other problem I'm having - which I'll worry about when the correct paths are being returned - is that I'm getting a memory access error when shifting the tiles in the third column down by one. I think it's getting confused when there's a block of tiles (2x2 or higher) rather than a path that's only ever a single tile wide.

Answer 1

You could use the BFS Algorithm and easily modify it to give you the longest path.

You've got a implementation example here. Or you've got at least SwiftStructures and SwiftGraph github repositories with graph and search algorithms already implemented in swift.

Answer 2

I can't fix your code, but i have an idea for a system that doesn't require recursion. You can try doing all possible paths from a reactor and block paths that you already traversed by being aware of the moves you have done when encountering a branch.

In the tile class, add another array of 4 integers initialized to 0 (called "dir" for example).

Pseudocode. Do a preprocess loop first:

foreach tiles:
  if tileHasNORTHNeighbor: tile.dir[0] = 1;
  if tileHasEASTNeighbor: tile.dir[1] = 1;
  if tileHasSOUTHNeighbor: tile.dir[2] = 1;
  if tileHasWESTNeighbor: tile.dir[3] = 1;

Then do:

tile currentTile = reactor;
array longest;
array temp;
tile lastBranch = reactor;
int lastMove = any key of "reactor.dir" with "1" as value;

function int countOnes(array dir):
  int count = 0;
  int t;
  for (t=0;t<4;t++):
     if dir[t]==1:
        count++;
  return count;


:start
if currentTile != reactor:
  if countOnes(currentTile.dir) > 2: //is branch
     lastBranch = currentTile;
  if countOnes(currentTile.dir) == 1: //is endpoint
     lastBranch.dir[lastMove] = 0; // block move out of the last branch found
     if longest.length < temp.length:
        longest = temp;
     currentTile = reactor; // return to reactor and redo
     array temp = []; //reset to empty array
     lastBranch = reactor;
     lastMove = next "reactor.dir" key with "1" as value;
     goto start;

if currentTile.dir[0] == 1:
  temp.append(currentTile);
  if countOnes(currentTile.dir) > 2:
     lastMove = 0;
  currentTile = getTileAtNORTH; //must avoid going backwards
  goto start;
if currentTile.dir[1] == 1:
  temp.append(currentTile);
  if countOnes(currentTile.dir) > 2:
     lastMove = 1;
  currentTile = getTileAtEAST; //must avoid going backwards
  goto start;
if currentTile.dir[2] == 1:
  temp.append(currentTile);
  if countOnes(currentTile.dir) > 2:
     lastMove = 2;
  currentTile = getTileAtSOUTH; //must avoid going backwards
  goto start;
if currentTile.dir[3] == 1:
  temp.append(currentTile);
  if countOnes(currentTile.dir) > 2:
     lastMove = 3;
  currentTile = getTileAtWEST; //must avoid going backwards
  goto start;