diff options
4 files changed, 97 insertions, 0 deletions
diff --git a/core/src/ch/asynk/gdx/boardgame/boards/Board.java b/core/src/ch/asynk/gdx/boardgame/boards/Board.java index 92756a1..0fde498 100644 --- a/core/src/ch/asynk/gdx/boardgame/boards/Board.java +++ b/core/src/ch/asynk/gdx/boardgame/boards/Board.java @@ -22,6 +22,8 @@ public interface Board extends TileKeyGenerator public int possibleMoves(Piece piece, Tile from, Collection<Tile> tiles); + public int shortestPath(Piece piece, Tile from, Tile to, Collection<Tile> tiles); + public boolean lineOfSight(int x0, int y0, int x1, int y1, Collection<Tile> tiles, Vector2 v); default public boolean lineOfSight(Tile from, Tile to, Collection<Tile> tiles, Vector2 v) diff --git a/core/src/ch/asynk/gdx/boardgame/boards/HexBoard.java b/core/src/ch/asynk/gdx/boardgame/boards/HexBoard.java index 8ddc2e1..76ad562 100644 --- a/core/src/ch/asynk/gdx/boardgame/boards/HexBoard.java +++ b/core/src/ch/asynk/gdx/boardgame/boards/HexBoard.java @@ -598,4 +598,85 @@ public class HexBoard implements Board return tiles.size(); } + + @Override public int shortestPath(Piece piece, Tile from, Tile to, Collection<Tile> tiles) + { + tiles.clear(); + searchCount += 1; + + from.acc = 0; + from.parent = null; + from.searchCount = searchCount; + + if (from == to || !from.isOnMap() || !to.isOnMap()) + return tiles.size(); + + int roadMarchBonus = piece.roadMarchBonus(); + from.roadMarch = roadMarchBonus > 0; + stack.push(from); + + while(!stack.isEmpty()) { + + final Tile src = stack.pop(); + + if (src == to) break; + + buildAdjacents(src.x, src.y); + for (int i = 0, j = 0; i < 6; i++, j++) { + final Tile dst = adjacents[i]; + if (!dst.isOnMap()) continue; + + if (getAngles()[j] == -1) j++; + final Orientation o = Orientation.fromR(getAngles()[j] + aOffset); + int cost = piece.moveCost(src, dst, o); + if (cost == Integer.MAX_VALUE) continue; // impracticable + cost += src.acc; + float total = cost + distance(dst.x, dst.y, to.x, to.y, Board.Geometry.EUCLIDEAN); + boolean rm = src.roadMarch && src.hasRoad(o); + if (rm) total -= roadMarchBonus; + + boolean add = false; + if (dst.searchCount != searchCount) { + dst.searchCount = searchCount; + add = true; + } else if ((dst.f > total) || (rm && !dst.roadMarch && dst.f == total)) { + stack.remove(dst); + add = true; + } + + if (add) { + dst.acc = cost; + dst.f = total; + dst.roadMarch = rm; + dst.parent = src; + int idx = Integer.MAX_VALUE; + for (int k = 0; k < stack.size(); k++) { + if (stack.get(k).f <= dst.f) { + idx = k; + break; + } + } + if (idx == Integer.MAX_VALUE) + stack.push(dst); + else + stack.insert(dst, idx); + } + } + } + + if (to.searchCount == searchCount) { + stack.clear(); + Tile t = to; + while(t != from) { + stack.add(t); + t = t.parent; + } + tiles.add(from); + while(!stack.isEmpty()) { + tiles.add(stack.pop()); + } + } + + return tiles.size(); + } } diff --git a/core/src/ch/asynk/gdx/boardgame/boards/SquareBoard.java b/core/src/ch/asynk/gdx/boardgame/boards/SquareBoard.java index 22afb9a..bede2ea 100644 --- a/core/src/ch/asynk/gdx/boardgame/boards/SquareBoard.java +++ b/core/src/ch/asynk/gdx/boardgame/boards/SquareBoard.java @@ -118,4 +118,11 @@ public class SquareBoard implements Board tiles.clear(); return tiles.size(); } + + @Override public int shortestPath(Piece piece, Tile from, Tile to, Collection<Tile> tiles) + { + System.err.println("NOT implemented yet."); + tiles.clear(); + return tiles.size(); + } } diff --git a/core/src/ch/asynk/gdx/boardgame/boards/TriangleBoard.java b/core/src/ch/asynk/gdx/boardgame/boards/TriangleBoard.java index dc3533a..e23bdec 100644 --- a/core/src/ch/asynk/gdx/boardgame/boards/TriangleBoard.java +++ b/core/src/ch/asynk/gdx/boardgame/boards/TriangleBoard.java @@ -187,4 +187,11 @@ public class TriangleBoard implements Board tiles.clear(); return tiles.size(); } + + @Override public int shortestPath(Piece piece, Tile from, Tile to, Collection<Tile> tiles) + { + System.err.println("NOT implemented yet."); + tiles.clear(); + return tiles.size(); + } } |