I have a simple Tile[,] that I populate with Rooms. Now I need to connect the rooms with a single tile wide corridor. At first I used A* to hook up the rooms but that, of course, get's the best path from tile to tile, but that's a bit boring.

So I decided to roll my own path walker, which very inefficiently get's me the same paths currently as A* except for some reason it never reaches the end tile. I was planning to add a randomness to it by adding a random chance to go in a random direction for a few steps before going back to it's route.

public static List<Tile> GetPath( Room startRoom, Room endRoom, Tile[,] map, int drunkenStep )
    //Select random tile from the wall list
    Tile startTile = startRoom.wallTiles[ UnityEngine.Random.Range( 0, startRoom.wallTiles.Count) ];
    Tile endTile = endRoom.wallTiles[   UnityEngine.Random.Range( 0, endRoom.wallTiles.Count) ];
    startRoom.wallTiles.Remove( startTile );
    endRoom.wallTiles.Remove( endTile );

    //Make it a floor tile
    startTile.type = RoomType.FLOOR;
    endTile.type = RoomType.FLOOR;
    startRoom.floorTiles.Add( startTile );
    endRoom.floorTiles.Add( endTile);

    //Add the start tile to the list 
    Tile selectedTile = startTile;
    List<Tile> path = new List<Tile>();
    path.Add( selectedTile );

    List<Tile> tilesToCheck = new List<Tile>();
        //loop four times for each adjascent tile
        for(int i = 0; i < 4; i++)
            int x = selectedTile.x + Convert.ToInt32( selectedTile.adj[i].x );
            int y = selectedTile.z + Convert.ToInt32( selectedTile.adj[i].y ); //x/y because 2D map. Tile y is for height displacement
            //Check if we are within bounds
            if( x < 0 || x > map.GetLength(0) || y < 0 || y > map.GetLength(1) ) continue;
            //We cant back track through a room and only use tiles that aren't set yet
            if( map[x,y].type == RoomType.NONE || (map[x,y].type == RoomType.FLOOR && map[x,y].roomId == -1) ) tilesToCheck.Add( map[x,y] );

        float minDist = Mathf.Infinity;
        Vector2 endPos = new Vector2( endTile.x, endTile.z );
        foreach (Tile t in tilesToCheck)
            float dist = Vector2.Distance( new Vector2( t.x, t.z), endPos);
            if (dist < minDist)
                selectedTile = t;
                minDist = dist;


    } while( selectedTile != endTile );

    return path;

Right now this never resolves and i'm not entirely sure why it doesnt reach the end tile. So my question is:

What is going wrong and what should I do to get straighter corridors and maybe some drunken randomness; maybe have a path loop around a little bit

Thanks for your time!


Your pathfinding would reach the room if this were true (when map[x,y] is endTile)

(map[x,y].type == RoomType.NONE || 
(map[x,y].type == RoomType.FLOOR && map[x,y].roomId == -1) )

You know the type property is RoomType.FLOOR, because you set it explicitly. So, the endTile.roomId is not -1.

  • \$\begingroup\$ aaaah good catch! It was 3 in the morning when i wrote that. Thank you. Any suggestions on making the path more varied? \$\endgroup\$
    – Superflat
    Aug 5 '13 at 11:05

Do you only want straight 1 wide corridors? If you're willing to have some more 'organic' paths I like using Drunk Walk to simulate some paths being natural fissures, or created by a burrowing/digging entity.

Drunk Walk: Given your start tile and end tile for the path step in the direction of the end tile 50% of the time otherwise move in a random direction. Every time you move into a Wall tile replace it with a Floor. The weights on the various directions can be changed, also you can have a preference to move in the one direction for a couple of steps.

Random-Path Generation: The other idea I like is to randomly generate a set of paths irrespective of your room locations (easy as picking two random points and drawing a line to connect them, repeat) then do pass to check that all your rooms are connected and if not either drop down more random paths, or apply your current algorithm.

  • \$\begingroup\$ I like your random path idea. Looking to applying noise to my map to simulate dense rock so the cost increases for those tiles. \$\endgroup\$
    – Superflat
    Aug 29 '13 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.