Skip to main content
Making it more in terms of gCost to make this easier to incorporate
Source Link
DMGregory
  • 141k
  • 23
  • 258
  • 401

Then I'd make a data structure to represent a state of a shipan A* node - with a few convenience methods to make it easier to compute neighbouring nodes I want frequently:

public struct MoveState {
    public readonly ShipTransform transform;
    public readonly int moveBudget;gCost;
    public float hCost;

    public MoveState(ShipTransform transform, int moveBudgetcost) {
        this.transform = transform;
        this.moveBudgetgCost = moveBudget;cost;
        hCost = 0;  // Our parent will fill this in later.
    }

    public MoveState SpendMove() {
        return new MoveState(transform, moveBudget - 1gCost+1);
    }

    public MoveState MoveForward() {
        return new MoveState(
            new ShipTransform(transform.position + ToOffset(transform.heading), transform.heading),
            moveBudgetgCost);
    }

    public MoveState Turn(Direction direction) {
        return new MoveState(
            new ShipTransform(transform.position, direction), 
            moveBudgetgCost);
    }
}
public static void FindMoves(MoveState start, List<MoveState> outcomes, Map map, int moveBudget) {        
    outcomes.Clear();

    // If we have no moves left, return with an empty list.
    if (start.moveBudgetgCost <>= 1moveBudget)
        return;

    // Add "wait" move (or move that cannot be completed).
    var here = start.SpendMove();
    outcomes.Add(here);

    // First, we'll try moving in our current heading.
    var forward = here.MoveForward();
            
    if (map.IsBlocked(forward.transform.position, forward.transform.heading)) {
        // If we're facing a barrier, we can only turn in-place.
        outcomes.Add(here.Turn(TurnLeft(here.transform.heading)));
        outcomes.Add(here.Turn(TurnRight(here.transform.heading)));
    } else {
        // Otherwise, we can move forward into the tile in front of us.
        outcomes.Add(forward);

        // And we can turn into the tiles left or right of it...
        var turned = forward.Turn(TurnLeft(here.transform.heading));
        var advanced = turned.MoveForward();            
        if (map.IsBlocked(advanced.transform.position, advanced.transform.heading)) {                
            // If that tile is blocked, we just turn our facing direction.
            outcomes.Add(turned);
        } else {
            // Otherwise, we move into the tile diagonal to our original.
            outcomes.Add(advanced);
        }

        // Repeat for a right turn.
        turned = forward.Turn(TurnRight(here.transform.heading));
        advanced = turned.MoveForward();
        if (map.IsBlocked(advanced.transform.position, advanced.transform.heading)) {
            outcomes.Add(advanced);
        } else {
            outcomes.Add(turned);
        }
    }

    // After we've moved, then the map takes a turn and can move us.
    for (int i = 0; i < outcomes.Count; i++) {
        // If we're on a tile that moves us, replace the outcome with that move.
        if (map.ProcessTileEffect(outcomes[i].transform, out ShipTransform result)) {
            outcomes[i] = new MoveState(result, outcomes[i].moveBudget);
        }
    }

    // Done!
}

YourAlso notice here that the costToReachgCost variable in this case should always beonly ever increments by 1 - because every move exhausts exactly one movement action slot, whether it's orthogonal or diagonal or a "wait".

Then I'd make a data structure to represent a state of a ship - with a few convenience methods to make it easier to compute neighbouring nodes I want frequently:

public struct MoveState {
    public readonly ShipTransform transform;
    public readonly int moveBudget;

    public MoveState(ShipTransform transform, int moveBudget) {
        this.transform = transform;
        this.moveBudget = moveBudget;
    }

    public MoveState SpendMove() {
        return new MoveState(transform, moveBudget - 1);
    }

    public MoveState MoveForward() {
        return new MoveState(
            new ShipTransform(transform.position + ToOffset(transform.heading), transform.heading),
            moveBudget);
    }

    public MoveState Turn(Direction direction) {
        return new MoveState(
            new ShipTransform(transform.position, direction), 
            moveBudget);
    }
}
public static void FindMoves(MoveState start, List<MoveState> outcomes, Map map) {        
    outcomes.Clear();

    // If we have no moves left, return with an empty list.
    if (start.moveBudget < 1)
        return;

    // Add "wait" move (or move that cannot be completed).
    var here = start.SpendMove();
    outcomes.Add(here);

    // First, we'll try moving in our current heading.
    var forward = here.MoveForward();
            
    if (map.IsBlocked(forward.transform.position, forward.transform.heading)) {
        // If we're facing a barrier, we can only turn in-place.
        outcomes.Add(here.Turn(TurnLeft(here.transform.heading)));
        outcomes.Add(here.Turn(TurnRight(here.transform.heading)));
    } else {
        // Otherwise, we can move forward into the tile in front of us.
        outcomes.Add(forward);

        // And we can turn into the tiles left or right of it...
        var turned = forward.Turn(TurnLeft(here.transform.heading));
        var advanced = turned.MoveForward();            
        if (map.IsBlocked(advanced.transform.position, advanced.transform.heading)) {                
            // If that tile is blocked, we just turn our facing direction.
            outcomes.Add(turned);
        } else {
            // Otherwise, we move into the tile diagonal to our original.
            outcomes.Add(advanced);
        }

        // Repeat for a right turn.
        turned = forward.Turn(TurnRight(here.transform.heading));
        advanced = turned.MoveForward();
        if (map.IsBlocked(advanced.transform.position, advanced.transform.heading)) {
            outcomes.Add(advanced);
        } else {
            outcomes.Add(turned);
        }
    }

    // After we've moved, then the map takes a turn and can move us.
    for (int i = 0; i < outcomes.Count; i++) {
        // If we're on a tile that moves us, replace the outcome with that move.
        if (map.ProcessTileEffect(outcomes[i].transform, out ShipTransform result)) {
            outcomes[i] = new MoveState(result, outcomes[i].moveBudget);
        }
    }

    // Done!
}

Your costToReach variable in this case should always be 1 - because every move exhausts exactly one movement action slot, whether it's orthogonal or diagonal or a "wait".

Then I'd make a data structure to represent an A* node - with a few convenience methods to make it easier to compute neighbouring nodes I want frequently:

public struct MoveState {
    public readonly ShipTransform transform;
    public readonly int gCost;
    public float hCost;

    public MoveState(ShipTransform transform, int cost) {
        this.transform = transform;
        gCost = cost;
        hCost = 0;  // Our parent will fill this in later.
    }

    public MoveState SpendMove() {
        return new MoveState(transform, gCost+1);
    }

    public MoveState MoveForward() {
        return new MoveState(
            new ShipTransform(transform.position + ToOffset(transform.heading), transform.heading),
            gCost);
    }

    public MoveState Turn(Direction direction) {
        return new MoveState(
            new ShipTransform(transform.position, direction), 
            gCost);
    }
}
public static void FindMoves(MoveState start, List<MoveState> outcomes, Map map, int moveBudget) {        
    outcomes.Clear();

    // If we have no moves left, return with an empty list.
    if (start.gCost >= moveBudget)
        return;

    // Add "wait" move (or move that cannot be completed).
    var here = start.SpendMove();
    outcomes.Add(here);

    // First, we'll try moving in our current heading.
    var forward = here.MoveForward();
            
    if (map.IsBlocked(forward.transform.position, forward.transform.heading)) {
        // If we're facing a barrier, we can only turn in-place.
        outcomes.Add(here.Turn(TurnLeft(here.transform.heading)));
        outcomes.Add(here.Turn(TurnRight(here.transform.heading)));
    } else {
        // Otherwise, we can move forward into the tile in front of us.
        outcomes.Add(forward);

        // And we can turn into the tiles left or right of it...
        var turned = forward.Turn(TurnLeft(here.transform.heading));
        var advanced = turned.MoveForward();            
        if (map.IsBlocked(advanced.transform.position, advanced.transform.heading)) {                
            // If that tile is blocked, we just turn our facing direction.
            outcomes.Add(turned);
        } else {
            // Otherwise, we move into the tile diagonal to our original.
            outcomes.Add(advanced);
        }

        // Repeat for a right turn.
        turned = forward.Turn(TurnRight(here.transform.heading));
        advanced = turned.MoveForward();
        if (map.IsBlocked(advanced.transform.position, advanced.transform.heading)) {
            outcomes.Add(advanced);
        } else {
            outcomes.Add(turned);
        }
    }

    // After we've moved, then the map takes a turn and can move us.
    for (int i = 0; i < outcomes.Count; i++) {
        // If we're on a tile that moves us, replace the outcome with that move.
        if (map.ProcessTileEffect(outcomes[i].transform, out ShipTransform result)) {
            outcomes[i] = new MoveState(result, outcomes[i].moveBudget);
        }
    }

    // Done!
}

Also notice here that the gCost only ever increments by 1 - because every move exhausts exactly one movement action slot, whether it's orthogonal or diagonal or a "wait".

Correcting whirlpool
Source Link
DMGregory
  • 141k
  • 23
  • 258
  • 401
public class Map {

    // I'll elide the map storage - you can use whatever format you like there.

    public bool IsBlocked(Vector2Int position, Direction travelDirection) {
        // TODO: Return true if there is a ship here that's not moving out of the way.            

        switch(GetTileTypeAt(position)) {
            case TileType.Rock: return true;
            case TileType.WhirlpoolNE: return travelDirection == Direction.West;
            case TileType.WhirlpoolSE: return travelDirection == Direction.North;
            case TileType.WhirlpoolSW: return travelDirection == Direction.East;
            case TileType.WhirlpoolNW: return travelDirection == Direction.South;
            default: return false;
        }
    }
    
    public bool ProcessTileEffect(ShipTransform transform, out ShipTransform result) {
        
        var tileType = GetTileTypeAt(transform.position);
        switch (tileType) {
            case TileType.WindNorth:    result = ProcessWind(transform, Direction.North);
                                        return true;
            case TileType.WindEast:     result = ProcessWind(transform, Direction.East);
                                        return true;
            case TileType.WindSouth:    result = ProcessWind(transform, Direction.South);
                                        return true;
            case TileType.WindWest:     result = ProcessWind(transform, Direction.West);
                                        return true;
            case TileType.WhirlpoolNE:  result = ProcessWhirlpool(transform, transform.position - Vector2Int.one);
                                        return true;
            case TileType.WhirlpoolNW:  result = ProcessWhirlpool(transform, transform.position + Vector2Int.down);
                                        return true;
            case TileType.WhirlpoolSE:  result = ProcessWhirlpool(transform, transform.position + Vector2Int.left);
                                        return true;
            case TileType.WhirlpoolSW:  result = ProcessWhirlpool(transform, transform.position);
                                        return true;
            default:                    result = transform;
                                        return false;
        }
    }

    ShipTransform ProcessWhirlpool(ShipTransform transform, Vector2Int whirlpoolCorner) {
        Vector2Int position = 2 * whirlpoolCorner + Vector2Int.one - transform.position;
        return new ShipTransform(position, TurnRight(transform.heading));
    }        

    ShipTransform ProcessWind(ShipTransform transform, Direction windDirection) {
        var position = transform.position + ToOffset(windDirection);

        if (IsBlocked(position, windDirection))
            return transform;

        return new ShipTransform(position, transform.heading);
    }
}
public class Map {

    // I'll elide the map storage - you can use whatever format you like there.

    public bool IsBlocked(Vector2Int position, Direction travelDirection) {
        // TODO: Return true if there is a ship here that's not moving out of the way.            

        switch(GetTileTypeAt(position)) {
            case TileType.Rock: return true;
            case TileType.WhirlpoolNE: return travelDirection == Direction.West;
            case TileType.WhirlpoolSE: return travelDirection == Direction.North;
            case TileType.WhirlpoolSW: return travelDirection == Direction.East;
            case TileType.WhirlpoolNW: return travelDirection == Direction.South;
            default: return false;
        }
    }
    
    public bool ProcessTileEffect(ShipTransform transform, out ShipTransform result) {
        
        var tileType = GetTileTypeAt(transform.position);
        switch (tileType) {
            case TileType.WindNorth:    result = ProcessWind(transform, Direction.North);
                                        return true;
            case TileType.WindEast:     result = ProcessWind(transform, Direction.East);
                                        return true;
            case TileType.WindSouth:    result = ProcessWind(transform, Direction.South);
                                        return true;
            case TileType.WindWest:     result = ProcessWind(transform, Direction.West);
                                        return true;
            case TileType.WhirlpoolNE:  result = ProcessWhirlpool(transform, transform.position - Vector2Int.one);
                                        return true;
            case TileType.WhirlpoolNW:  result = ProcessWhirlpool(transform, transform.position + Vector2Int.down);
                                        return true;
            case TileType.WhirlpoolSE:  result = ProcessWhirlpool(transform, transform.position + Vector2Int.left);
                                        return true;
            case TileType.WhirlpoolSW:  result = ProcessWhirlpool(transform, transform.position);
                                        return true;
            default:                    result = transform;
                                        return false;
        }
    }

    ShipTransform ProcessWhirlpool(ShipTransform transform, Vector2Int whirlpoolCorner) {
        Vector2Int position = whirlpoolCorner + Vector2Int.one - transform.position;
        return new ShipTransform(position, TurnRight(transform.heading));
    }        

    ShipTransform ProcessWind(ShipTransform transform, Direction windDirection) {
        var position = transform.position + ToOffset(windDirection);

        if (IsBlocked(position, windDirection))
            return transform;

        return new ShipTransform(position, transform.heading);
    }
}
public class Map {

    // I'll elide the map storage - you can use whatever format you like there.

    public bool IsBlocked(Vector2Int position, Direction travelDirection) {
        // TODO: Return true if there is a ship here that's not moving out of the way.            

        switch(GetTileTypeAt(position)) {
            case TileType.Rock: return true;
            case TileType.WhirlpoolNE: return travelDirection == Direction.West;
            case TileType.WhirlpoolSE: return travelDirection == Direction.North;
            case TileType.WhirlpoolSW: return travelDirection == Direction.East;
            case TileType.WhirlpoolNW: return travelDirection == Direction.South;
            default: return false;
        }
    }
    
    public bool ProcessTileEffect(ShipTransform transform, out ShipTransform result) {
        
        var tileType = GetTileTypeAt(transform.position);
        switch (tileType) {
            case TileType.WindNorth:    result = ProcessWind(transform, Direction.North);
                                        return true;
            case TileType.WindEast:     result = ProcessWind(transform, Direction.East);
                                        return true;
            case TileType.WindSouth:    result = ProcessWind(transform, Direction.South);
                                        return true;
            case TileType.WindWest:     result = ProcessWind(transform, Direction.West);
                                        return true;
            case TileType.WhirlpoolNE:  result = ProcessWhirlpool(transform, transform.position - Vector2Int.one);
                                        return true;
            case TileType.WhirlpoolNW:  result = ProcessWhirlpool(transform, transform.position + Vector2Int.down);
                                        return true;
            case TileType.WhirlpoolSE:  result = ProcessWhirlpool(transform, transform.position + Vector2Int.left);
                                        return true;
            case TileType.WhirlpoolSW:  result = ProcessWhirlpool(transform, transform.position);
                                        return true;
            default:                    result = transform;
                                        return false;
        }
    }

    ShipTransform ProcessWhirlpool(ShipTransform transform, Vector2Int whirlpoolCorner) {
        Vector2Int position = 2 * whirlpoolCorner + Vector2Int.one - transform.position;
        return new ShipTransform(position, TurnRight(transform.heading));
    }        

    ShipTransform ProcessWind(ShipTransform transform, Direction windDirection) {
        var position = transform.position + ToOffset(windDirection);

        if (IsBlocked(position, windDirection))
            return transform;

        return new ShipTransform(position, transform.heading);
    }
}
Source Link
DMGregory
  • 141k
  • 23
  • 258
  • 401

I'll show you how I'd tackle this in C#, since it's the language I'm most familiar with and I'm less likely to make silly syntax errors. 😉 Java syntax is very similar, so you should be able to translate the strategy to your code smoothly enough.

I'd start by defining some data types to manipulate ship positions and headings. Nothing too exciting here.

public enum Direction {
    North,
    East,
    South,
    West
}    

public static Direction TurnRight(Direction direction) {
    return (Direction)(((int)direction + 1) & 3);
}

public static Direction TurnLeft(Direction direction) {
    return (Direction)(((int)direction + 3) & 3);
}

public static Vector2Int ToOffset(Direction direction) {
    switch(direction) {
        case Direction.North: return Vector2Int.up;
        case Direction.East: return Vector2Int.right;
        case Direction.South: return Vector2Int.down;
        case Direction.West: return Vector2Int.left;            
    }
    throw new System.ArgumentException($"Invalid direction {direction}");
}

public struct ShipTransform {
    public readonly Vector2Int position;
    public readonly Direction heading;

    public ShipTransform(Vector2Int position, Direction heading) {
        this.position = position;
        this.heading = heading;
    }
}

Then I'd set up the map functions to compute what happens for special effect tiles...

public class Map {

    // I'll elide the map storage - you can use whatever format you like there.

    public bool IsBlocked(Vector2Int position, Direction travelDirection) {
        // TODO: Return true if there is a ship here that's not moving out of the way.            

        switch(GetTileTypeAt(position)) {
            case TileType.Rock: return true;
            case TileType.WhirlpoolNE: return travelDirection == Direction.West;
            case TileType.WhirlpoolSE: return travelDirection == Direction.North;
            case TileType.WhirlpoolSW: return travelDirection == Direction.East;
            case TileType.WhirlpoolNW: return travelDirection == Direction.South;
            default: return false;
        }
    }
    
    public bool ProcessTileEffect(ShipTransform transform, out ShipTransform result) {
        
        var tileType = GetTileTypeAt(transform.position);
        switch (tileType) {
            case TileType.WindNorth:    result = ProcessWind(transform, Direction.North);
                                        return true;
            case TileType.WindEast:     result = ProcessWind(transform, Direction.East);
                                        return true;
            case TileType.WindSouth:    result = ProcessWind(transform, Direction.South);
                                        return true;
            case TileType.WindWest:     result = ProcessWind(transform, Direction.West);
                                        return true;
            case TileType.WhirlpoolNE:  result = ProcessWhirlpool(transform, transform.position - Vector2Int.one);
                                        return true;
            case TileType.WhirlpoolNW:  result = ProcessWhirlpool(transform, transform.position + Vector2Int.down);
                                        return true;
            case TileType.WhirlpoolSE:  result = ProcessWhirlpool(transform, transform.position + Vector2Int.left);
                                        return true;
            case TileType.WhirlpoolSW:  result = ProcessWhirlpool(transform, transform.position);
                                        return true;
            default:                    result = transform;
                                        return false;
        }
    }

    ShipTransform ProcessWhirlpool(ShipTransform transform, Vector2Int whirlpoolCorner) {
        Vector2Int position = whirlpoolCorner + Vector2Int.one - transform.position;
        return new ShipTransform(position, TurnRight(transform.heading));
    }        

    ShipTransform ProcessWind(ShipTransform transform, Direction windDirection) {
        var position = transform.position + ToOffset(windDirection);

        if (IsBlocked(position, windDirection))
            return transform;

        return new ShipTransform(position, transform.heading);
    }
}

Then I'd make a data structure to represent a state of a ship - with a few convenience methods to make it easier to compute neighbouring nodes I want frequently:

public struct MoveState {
    public readonly ShipTransform transform;
    public readonly int moveBudget;

    public MoveState(ShipTransform transform, int moveBudget) {
        this.transform = transform;
        this.moveBudget = moveBudget;
    }

    public MoveState SpendMove() {
        return new MoveState(transform, moveBudget - 1);
    }

    public MoveState MoveForward() {
        return new MoveState(
            new ShipTransform(transform.position + ToOffset(transform.heading), transform.heading),
            moveBudget);
    }

    public MoveState Turn(Direction direction) {
        return new MoveState(
            new ShipTransform(transform.position, direction), 
            moveBudget);
    }
}

Now we can make a method that enumerates the moves we can make from a given position:

public static void FindMoves(MoveState start, List<MoveState> outcomes, Map map) {        
    outcomes.Clear();

    // If we have no moves left, return with an empty list.
    if (start.moveBudget < 1)
        return;

    // Add "wait" move (or move that cannot be completed).
    var here = start.SpendMove();
    outcomes.Add(here);

    // First, we'll try moving in our current heading.
    var forward = here.MoveForward();
            
    if (map.IsBlocked(forward.transform.position, forward.transform.heading)) {
        // If we're facing a barrier, we can only turn in-place.
        outcomes.Add(here.Turn(TurnLeft(here.transform.heading)));
        outcomes.Add(here.Turn(TurnRight(here.transform.heading)));
    } else {
        // Otherwise, we can move forward into the tile in front of us.
        outcomes.Add(forward);

        // And we can turn into the tiles left or right of it...
        var turned = forward.Turn(TurnLeft(here.transform.heading));
        var advanced = turned.MoveForward();            
        if (map.IsBlocked(advanced.transform.position, advanced.transform.heading)) {                
            // If that tile is blocked, we just turn our facing direction.
            outcomes.Add(turned);
        } else {
            // Otherwise, we move into the tile diagonal to our original.
            outcomes.Add(advanced);
        }

        // Repeat for a right turn.
        turned = forward.Turn(TurnRight(here.transform.heading));
        advanced = turned.MoveForward();
        if (map.IsBlocked(advanced.transform.position, advanced.transform.heading)) {
            outcomes.Add(advanced);
        } else {
            outcomes.Add(turned);
        }
    }

    // After we've moved, then the map takes a turn and can move us.
    for (int i = 0; i < outcomes.Count; i++) {
        // If we're on a tile that moves us, replace the outcome with that move.
        if (map.ProcessTileEffect(outcomes[i].transform, out ShipTransform result)) {
            outcomes[i] = new MoveState(result, outcomes[i].moveBudget);
        }
    }

    // Done!
}

Note that nowhere in here does the algorithm consider what the AI "should" do per se. It only exhaustively enumerates the set of things that could happen.

Your costToReach variable in this case should always be 1 - because every move exhausts exactly one movement action slot, whether it's orthogonal or diagonal or a "wait".