Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

A* Pathfinding over multiple grids

I'm attempting to implement A* pathfinding around a cube, the cube is made up of 6 grids and to keep it simple I have 4 methods GetXPlus, GetXMinus, GetYPlus, GetYMinus. Each method checks to see if the next tile is within the current grid space, if its not it switches to the appropriate grid.

The problem I'm having is when attempting to get a tile from a grid that is flipped the other way from the current grid, the tile returned is on the opposite side. Is there a way or approach which would allow me to avoid writing unique logic for every single origin grid and direction?

To help articulate my problem, In this I have originated from the (purple) grid and are using the GetXPlus method :

enter image description here

A snippit of my current implementation (each grid is 64 by 64):

public Tile GetXPlus( int currentX, int currentY )
{
    var newX = currentX + 1;
    var tile = GetTile( newX , currentY );

    if( newX > 64 ) //Get adjacent XPlus Grid 
    { 
        currentGrid = SetCurrentGrid( XPlusGridIndex );
        tile = GetTile( newX - 64, currentY );
    }

    return tile;
}

Background

This implementation originated from an excellent answer to a different question suggested here: https://gamedev.stackexchange.com/questions/53866/pathfinding-on-a-uneven-planetary-surface

like image 357
Caius Eugene Avatar asked Apr 18 '13 17:04

Caius Eugene


1 Answers

I would suggest that you go even further than suggested by the previous answer. Create a cube that represents all tiles, and that you cache the neighbours of every tile. As the relations between tiles are fixed, it will safe you a lot of time.

Afterwords you can use a double[,,] or int[,,,] to keep track of your processed tiles, and based on that add neighbours to your Queue<Tile>.

If needed you can implement GetDirection(Tile tile) too. That function only have to search at the directions dictionary.

public class Cube { private Tile[,,] tiles;

    public Cube(int size)
    {
        tiles = new Tile[size, size, 6];

        // initialize.
        for (var side = 0; side < 6; side++)
        {
            for (var x = 0; x < size; x++)
            {
                for (var y = 0; y < size; y++)
                {
                    tiles[x, y, side] = new Tile(x, y, side);
                }
            }
        }

        // set directions & neighbors
        for (var side = 0; side < 6; side++)
        {
            for (var x = 0; x < size; x++)
            {
                for (var y = 0; y < size; y++)
                {
                    // todo: implement.
                }
            }
        }
    }

    public Tile this[int x, int y, int side]
    {
        get
        {
            return tiles[x, y, side];
        }
    }
}

public class Tile
{
    private Dictionary<DirectionType, Tile> directions = new Dictionary<DirectionType, Tile>();

    private Tile[] neighbors = new Tile[4];

    public Tile(int x, int y, int side)
    {
        this.X = x;
        this.Y = y;
        this.Side = side;
    }

    public int X { get; private set; }
    public int Y { get; private set; }
    public int Side { get; private set; }

    public Tile this[DirectionType dir]
    {
        get
        {
            return directions[dir];
        }
    }



    public Tile[] Neighbors { get { return neighbors; } }
}

public enum DirectionType
{
    // delta: +1, 0
    e,
    // delta: 0, +1
    n,
    // delta: -1, 0
    w,
    // delta: 0, -1
    s,
    // delta: 0, 0
    X
}
like image 106
Corniel Nobel Avatar answered Sep 29 '22 02:09

Corniel Nobel