Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
aaaah good catch! It was 3 in the morning when i wrote that. Thank you. Any suggestions on making the path more varied? –  Superflat Aug 5 '13 at 11:05
add comment

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.

share|improve this answer
    
I like your random path idea. Looking to applying noise to my map to simulate dense rock so the cost increases for those tiles. –  Superflat Aug 29 '13 at 0:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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