public Troop(int troops, GraphPath<Tile> path) { this.troops = troops; this.path = new DefaultGraphPath<>(); for (Tile tile : path) { this.path.add(tile); } texture = Assets.TROOP; setSize(texture.getRegionWidth(), texture.getRegionHeight()); label = new ConquestLabel(this.troops, getX(), getY(), getWidth(), getHeight()); setOrigin(Align.center); createActions(); }
@Test public void searchNodePath_WhenDestinationUnreachable_ExpectedNoOuputPathFound () { // @off - disable libgdx formatter final String graphDrawing = ".....#....\n" + ".....#....\n" + ".....#...."; // @on - enable libgdx formatter final MyGraph graph = createGraphFromTextRepresentation(graphDrawing); final IndexedAStarPathFinder<MyNode> pathfinder = new IndexedAStarPathFinder<>(graph); final GraphPath<MyNode> outPath = new DefaultGraphPath<>(); // @off - disable libgdx formatter // 0123456789 // S....#...E 0 // .....#.... 10 // .....#.... 20 // @on - enable libgdx formatter final boolean searchResult = pathfinder.searchNodePath(graph.nodes.get(0), graph.nodes.get(9), new ManhattanDistance(), outPath); Assert.assertFalse("Unexpected search result", searchResult); }
public Pathway(Array<Tile> tiles, Owner owner) { start = new Array<>(); Map map = new Map(tiles.size, owner); pathFinder = new IndexedAStarPathFinder<>(map); heuristic = new EuclidianHeuristic(); graphPath = new DefaultGraphPath<>(); }
public TileCoordinate getNextTarget(final TileCoordinate location, final TileCoordinate destination) { final GraphPath<Connection<TileCoordinate>> path = new DefaultGraphPath<>(); pathFinder.searchConnectionPath( graph.getCachedNode(location), graph.getCachedNode(destination), heuristic, path ); return path.getCount() == 0 ? null : path.get(0).getToNode(); }
public static void main(String[] args) { // @off - disable libgdx formatter final String graphDrawing = ".....#....\n" + ".....#....\n" + ".....#...."; // @on - enable libgdx formatter final MyGraph graph = createGraphFromTextRepresentation(graphDrawing); final IndexedAStarPathFinder<MyNode> pathfinder = new IndexedAStarPathFinder<MyNode>(graph); final GraphPath<MyNode> outPath = new DefaultGraphPath<MyNode>(); // @off - disable libgdx formatter // 0123456789 // S....#...E 0 // .....#.... 10 // .....#.... 20 // @on - enable libgdx formatter final boolean searchResult = pathfinder.searchNodePath(graph.getNodes().get(0), graph.getNodes().get(20), new ManhattanDistance(), outPath); System.out.println(""+searchResult); System.out.println(""+outPath.getCount()); for(int i=0;i<outPath.getCount();i++){ System.out.println(""+outPath.get(i)); } }
@Override public void create() { mShapeRenderer = new ShapeRenderer(); mGraph = new TestGraph(20); mPath = new DefaultGraphPath<TestNode>(); mHeuristic = new ManhattanDistanceHeuristic(); // Initialize all the nodes that should be present. int index = 0; //Used to set index for every node. for (int x = 0; x < mMap.length; x++) { for (int y = 0; y < mMap[0].length; y++) { if (mMap[x][y] == 1) { mNodes[x][y] = new TestNode(x*TestNode.TILE_SIZE, y*TestNode.TILE_SIZE, index++); mGraph.addNode(mNodes[x][y]); } } } // Add connection to every neighbour of this node. for (int x = 0; x < mNodes.length; x++) { for (int y = 0; y < mNodes[0].length; y++) { if (null != mNodes[x][y]) { addNodeNeighbour(mNodes[x][y], x - 1, y); // Node to left addNodeNeighbour(mNodes[x][y], x + 1, y); // Node to right addNodeNeighbour(mNodes[x][y], x, y - 1); // Node below addNodeNeighbour(mNodes[x][y], x, y + 1); // Node above } } } mPathFinder = new IndexedAStarPathFinder<TestNode>(mGraph, true); calculatePath(); }
public AStartPathFinding(AStarMap map) { this.map = map; this.pathfinder = new IndexedAStarPathFinder<Node>(createGraph(map)); this.connectionPath = new DefaultGraphPath<Connection<Node>>(); this.heuristic = new Heuristic<Node>() { @Override public float estimate (Node node, Node endNode) { // Manhattan distance return Math.abs(endNode.x - node.x) + Math.abs(endNode.y - node.y); } }; }
public void touchToMove(int screenX, int screenY) { Vector3 input = new Vector3(screenX, screenY, 0); camera.unproject(input); int x = MathUtils.floor(input.x / 32); int y = MathUtils.floor(input.y / 32); Gdx.app.debug(TAG, "clicked # (x:" + x + ",y:" + y + " )"); //we click not npc or block,set aim to move if (!isCollisionWithNpc(x, y) && !isCollisionWithBlock(x, y)) { //A* path finding path.clear(); Vector2 start = new Vector2(MathUtils.round(player.getX() / 32), MathUtils.round(player.getY() / 32)); //we need set exactly start position Vector2 end = new Vector2(x, y); int numCols = mapMgr.cols; int numRows = mapMgr.rows; Gdx.app.debug(TAG, "From:" + start + " to " + end + "|numCols:" + numCols + "|numRows:" + numRows); int s = (int) start.x + ((int) start.y) * numCols; int t = (int) end.x + ((int) (end.y)) * numCols; List<Sprite> temp = new ArrayList<Sprite>(); temp.addAll(mapMgr.npcs); temp.addAll(mapMgr.enemies); // temp.addAll(mapMgr.events); final MyGraph graph = GraphGenerator.generateGraph(mapMgr.getBlockLayer(), temp, numCols, numRows, 32, 32, start); final IndexedAStarPathFinder<MyNode> pathfinder = new IndexedAStarPathFinder<MyNode>(graph); final GraphPath<MyNode> outPath = new DefaultGraphPath<MyNode>(); final boolean searchResult = pathfinder.searchNodePath(graph.getNodes().get(s), graph.getNodes().get(t), new ManhattanDistance(), outPath); MyPathSmoother pathSmoother = new MyPathSmoother(new MyRaycastCollisionDetector(graph)); pathSmoother.smoothPath(outPath); StringBuilder sb = new StringBuilder(); for (int i = outPath.getCount() - 1; i >= 0; i--) { sb.append("(" + outPath.get(i).getX() + "," + outPath.get(i).getY() + ")|"); path.add(outPath.get(i)); } if (searchResult) { Gdx.app.debug(TAG, "Start Follow Path:" + sb.toString()); player.followPath(path); aim = new Aim(x, y); } } else { aim = null; } }
@Test public void searchNodePath_WhenSearchingAdjacentTile_ExpectedOuputPathLengthEquals2 () { // @off - disable libgdx formatter final String graphDrawing = "..........\n" + "..........\n" + ".........."; // @on - enable libgdx formatter final MyGraph graph = createGraphFromTextRepresentation(graphDrawing); final IndexedAStarPathFinder<MyNode> pathfinder = new IndexedAStarPathFinder<>(graph); final GraphPath<MyNode> outPath = new DefaultGraphPath<>(); // @off - disable libgdx formatter // 0123456789 // .......... 0 // .....S.... 10 // .....E.... 20 // @on - enable libgdx formatter final boolean searchResult1 = pathfinder.searchNodePath(graph.nodes.get(15), graph.nodes.get(25), new ManhattanDistance(), outPath); Assert.assertTrue("Unexpected search result", searchResult1); Assert.assertEquals("Unexpected number of nodes in path", 2, outPath.getCount()); // @off - disable libgdx formatter // 0123456789 // .......... 0 // .....SE... 10 // .......... 20 // @on - enable libgdx formatter outPath.clear(); final boolean searchResult2 = pathfinder.searchNodePath(graph.nodes.get(15), graph.nodes.get(16), new ManhattanDistance(), outPath); Assert.assertTrue("Unexpected search result", searchResult2); Assert.assertEquals("Unexpected number of nodes in path", 2, outPath.getCount()); // @off - disable libgdx formatter // 0123456789 // .......... 0 // ....ES.... 10 // .......... 20 // @on - enable libgdx formatter outPath.clear(); final boolean searchResult3 = pathfinder.searchNodePath(graph.nodes.get(15), graph.nodes.get(14), new ManhattanDistance(), outPath); Assert.assertTrue("Unexpected search result", searchResult3); Assert.assertEquals("Unexpected number of nodes in path", 2, outPath.getCount()); // @off - disable libgdx formatter // 0123456789 // .....E.... 0 // .....S.... 10 // .......... 20 // @on - enable libgdx formatter outPath.clear(); final boolean searchResult4 = pathfinder.searchNodePath(graph.nodes.get(15), graph.nodes.get(5), new ManhattanDistance(), outPath); Assert.assertTrue("Unexpected search result", searchResult4); Assert.assertEquals("Unexpected number of nodes in path", 2, outPath.getCount()); }
@Test public void searchNodePath_WhenSearchCanHitDeadEnds_ExpectedOuputPathFound () { // @off - disable libgdx formatter final String graphDrawing = ".#.#.......#..#...............\n" + ".#............#.....#..#####..\n" + "...#.#######..#.....#.........\n" + ".#.#.#........#.....########..\n" + ".###.#....#####.....#......##.\n" + ".#...#....#.........#...##....\n" + ".#####....#.........#....#....\n" + ".#........#.........#....#####\n" + ".####....##.........#......#..\n" + "....#...............#......#.."; // @on - enable libgdx formatter final MyGraph graph = createGraphFromTextRepresentation(graphDrawing); final IndexedAStarPathFinder<MyNode> pathfinder = new IndexedAStarPathFinder<>(graph); final GraphPath<MyNode> outPath = new DefaultGraphPath<>(); // @off - disable libgdx formatter // 012345678901234567890123456789 // S#.#.......#..#............... 0 // .#............#.....#..#####.. 30 // ...#.#######..#.....#......... 60 // .#.#.#........#.....########.. 90 // .###.#....#####.....#......##. 120 // .#...#....#.........#...##.... 150 // .#####....#.........#....#.... 180 // .#E.......#.........#....##### 210 // .####....##.........#......#.. 240 // ....#...............#......#.. 270 // @on - enable libgdx formatter final boolean searchResult = pathfinder.searchNodePath(graph.nodes.get(0), graph.nodes.get(212), new ManhattanDistance(), outPath); Assert.assertTrue("Unexpected search result", searchResult); Assert.assertEquals("Unexpected number of nodes in path", 32, outPath.getCount()); }
public List<IntPair> getPath(int levelID, IntPair from, IntPair to) { graph = new Graph(128); path = new DefaultGraphPath<Node>(); heuristic = new DistHeuristic(); Level level = Game_AI_TestBed.instance().getLevel(levelID); nodes = new Node[level.getTileSizeX()][level.getTileSizeY()]; int index = 0; for (int x = 0; x < level.getTileSizeX(); x++) { for (int y = 0; y < level.getTileSizeY(); y++) { if (level.isTilePassable(x, y)) { nodes[x][y] = new Node(x*Cst.TILESIZE, y*Cst.TILESIZE, index++); graph.addNode(nodes[x][y]); } } } for (int x = 0; x < nodes.length; x++) { for (int y = 0; y < nodes[0].length; y++) { if (null != nodes[x][y]) { addNodeNeighbour(nodes, nodes[x][y], x - 1, y); addNodeNeighbour(nodes, nodes[x][y], x + 1, y); addNodeNeighbour(nodes, nodes[x][y], x, y - 1); addNodeNeighbour(nodes, nodes[x][y], x, y + 1); } } } pathFinder = new IndexedAStarPathFinder<Node>(graph, true); return calcPath(from, to); }
@Override public void run() { if (!finished) { if (request == null) { if (!a.isActive() || !b.isActive()) { finished=true; return; } // offset to center on the image, and convert to pathing space. // @todo cleanup the space difference. final Pos posA = mPos.get(a); final Pos posB = mPos.get(b); Bounds boundsA = mBounds.get(a); Bounds boundsB = mBounds.get(b); int aX = (int) (posA.x + boundsA.cx()) / LayerManager.CELL_SIZE; int aY = (int) (posA.y + boundsA.cy()) / LayerManager.CELL_SIZE; final GridNode cellA = graph.get(aX, aY); int bX = (int) (posB.x + boundsB.cx()) / LayerManager.CELL_SIZE; int bY = (int) (posB.y + boundsB.cy()) / LayerManager.CELL_SIZE; final GridNode cellB = graph.get(bX, bY); entityA().setX(aX); entityA().setY(aY); entityB().setX(bX); entityB().setY(bY); if ( cellA == null || cellB == null ) { finished=true; return; } request = new PathFinderRequest<GridNode>(cellA, cellB, new GridNodeEuclideanHeuristic(), new DefaultGraphPath<GridNode>(128)); request.changeStatus(PathFinderRequest.SEARCH_INITIALIZED); } if ( finder.search(request, TimeUtils.millisToNanos(MAX_RUNTIME_MS))) { finished = true; if (request.pathFound) { generatePath(request.resultPath); request = null; } } if ( request != null ) request.statusChanged = false; } }