2
\$\begingroup\$

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:

board state 1

(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:

board state 2

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
    }
}
\$\endgroup\$
4
  • 4
    \$\begingroup\$ What should the result be for non-tree paths, for example the "P" shape? \$\endgroup\$
    – wondra
    Feb 4, 2016 at 11:52
  • \$\begingroup\$ That depends on the position of the reactor; if it starts at the bottom of the P, it'll go either all the way up then round, or hang a right at the bottom of the loop and follow up and around back down to where it turned right. If it starts mid-P (at the top, or where the curve joins midway) and the available paths are of equal lengths, it'll pick one at random. Each tile in any given path should only be visited once \$\endgroup\$ Feb 4, 2016 at 12:03
  • 1
    \$\begingroup\$ Finding longest cycle-free paths is an NP-Hard problem. It'll still be tractable in this case because your graphs are small, but don't underestimate how thorny this problem can be. Because you want longest paths, many common path algorithms like Dijkstra's will give you the wrong answer without modification. \$\endgroup\$
    – DMGregory
    Feb 4, 2016 at 14:32
  • \$\begingroup\$ I've added some code above. I think I'm closing in on a solution but my code is bugged... \$\endgroup\$ Feb 12, 2016 at 9:24

1 Answer 1

3
\$\begingroup\$

If I am not mistaken these types of problems are usually solved by backtracking family of algorithms.
I would use an algorithm similar to DFS: recursively search the solutions tree and whenever leaf node is reached, save the path if it was the longest discovered. After reaching leaf node, backtrack to last "crossroads" and take the other turn(s). In order to prevent infinite loops you will also need to mark visited/searched nodes.


edit: adding C++ code example what I had in mind. I would maintain two integers forward and backward depth, first one being used to detect maximal depth found and as tile index in path, while the second is used to to detect backtracking from furthest path:

//simplified tile
struct Tile {
  int x,y,type;
  bool used;
}
//check for correct coords, same type and is not used. if not valid, return null
Tile* getValidTileAt(int x, int y, int type) { ... }

std::vector<Tile*> findLongestPath(Tile& tile) {
  std::vector<Tile*> path;//or pre-allocate array "long enough"
  int max_depth = -1;
  search(tile.x, tile.y, type, 0, max_depth, path);
  return path;
}
//max_depth must be globally available as well as the path -> passing refrences 
int search(int x, int y, int type, int depth, int& max_depth, std::vector<Tile*>& path)
{
  var tile = getValidTileAt(x, y, type);
  if(!tile) return depth - 1; //not valid tile, return
  tile->used = true; //maintain used flag any way you find fit
  int branch_max = depth;
  if(branch_max > max_depth) //found new furthest tile
  {
    max_depth = branch_max;
    path.push_back(tile);//or if(branch_max  == depth) path.reserve(depth +1);
  }
  //search neighbours in *set order*
  branch_max = max(branch_max , search(x, y - 1, type, depth + 1, max_depth, path));
  branch_max = max(branch_max , search(x - 1, y, type, depth + 1, max_depth, path));
  branch_max = max(branch_max , search(x, y + 1, type, depth + 1, max_depth, path));
  branch_max = max(branch_max , search(x + 1, y, type, depth + 1, max_depth, path));

  //backtracking from longest branch, overwrite path
  if(branch_max == max_depth) path[depth] = tile; 
  tile->used = false;
  return branch_max;
}

note: did not run the code crtl+c/v at on risk

\$\endgroup\$
7
  • \$\begingroup\$ As DMGregory pointed out in comments of question, dont let this problem (and algorithm) fool you. Even though it is derived from DFS, this is bruteforce algorithm (inspired by one of the Hamilton path problem algorithms if anybody is interested in further research). \$\endgroup\$
    – wondra
    Feb 4, 2016 at 15:26
  • \$\begingroup\$ I think I may have a solution using Graphs and Depth-First Search, as per your suggestion. I'm going to start off by using the code found here: alexanderuseche.com/search-algorithms-depth-first-search. I'll step through connected nodes starting from the reactor, and add them to the graph. Then I'll step through the graph and assign depth values, then find the route from the reactor that achieves the highest score. That, in my estimation, should work for my purposes... unless I'm missing something really obvious. \$\endgroup\$ Feb 5, 2016 at 10:25
  • \$\begingroup\$ @MassivePenguin this is why I asked about the "P" shape - simple DFS will not return global optimum(the best result) for input with cycles. You can ignore the chords but it will probably fail for anything more complex anyway. If you need correct(=best, longest) results for all inputs I am afraid you will need to backtrack one way or another. \$\endgroup\$
    – wondra
    Feb 6, 2016 at 13:50
  • \$\begingroup\$ I've added some code to my example above - I think I'm getting close to a solution but the function isn't pruning shorter paths like it should. \$\endgroup\$ Feb 12, 2016 at 9:23
  • \$\begingroup\$ @MassivePenguin sorry, I dont speak that programming language so I cannot check for errors, however I would make sure to copy the current(if loneger) into the longest - longestPath = tempPath looks like you are only copying reference not the path itself(again, I do not know the language, maybe it is already deep copying). Hope it helps. \$\endgroup\$
    – wondra
    Feb 12, 2016 at 11:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .