1
\$\begingroup\$

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>();
    do
    {
        //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;
            }
        }

        path.Add(selectedTile);
        tilesToCheck.Clear();

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

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

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.

\$\endgroup\$
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, 2013 at 11:05
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\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, 2013 at 0:17

You must log in to answer this question.

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