Board : implement shortestPath() for HexBoards

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();
+    }
 }