Tag Info

New answers tagged

8

Actually A* does not use dimensions. A* works with nodes and each nodes have paths to other nodes. In the case of a 2D grid every cell is a node and every boundary is an implicit path (left, right, up, down, and/or diagonals), the key here is that it is implicit. This is a trick to reduce the memory footprint, but A* itself does not require a 2D or 3D ...


0

A* is not designed to deal directly with realtime physics paths as there's a near infinite number of possible paths. walk 0.00001 units and jump walk 0.00002 units and jump walk 0.00003 units and jump ... You will first need to build a reduced list of path nodes to limit the possibilities. Every platforms start with 2 nodes with a path between, then add ...


1

You need to keep a enemy heading (direction) variable and only move the enemy along that direction. Slowly rotate the enemy heading to face where it actually wants to go but only a few degrees per frame. You move forward according to the dot product of the heading and where you should be heading. This prevents overshooting the target. The enemy will move a ...


0

You just need to modify your A* implementation to exit when there are no acceptable tiles left and save all tiles meeting the condition. Start as usual and set a MaxCost value (that is max distance unit can walk). Then iterate possible tiles to go and add ones that are passable and whose cost is less than or equal than MaxCost to a list. Algorithm ends when ...


1

I'm going to copy paste some basic code, I came up with in case it helps anyone private function hillClimbing( pathCells: Array): Array { var pathVectors: Array = new Array; for(var k:int=0;k<pathCells.length;k++) { pathVectors.push(pathCells[k].position); } trace( "path length before", ...


0

Instead of using A-star from each zombie to the player, use a breadth-first (ie Dijstra's) out from the player, and as you encounter each zombie assign it the current best path. Have each zombie ignore other zombies for pathfinding but skip a step if the next node is occupied by a zombie.


0

If you know the shape of the piece, and you know where you want to place it, I would assume you have determined the orientation of the piece already. If this is the case then I think the solution is fairly straight forward. You have a default orientation for each piece, and depending on the piece 0-3 possible alternate orientations. The number of rotations ...


4

I added another answer for an alternative explanation of the problem. You can think of this problem as Motion Planning in the Configuration Space of the tetris piece. The Configuration Space Define the configuration of a Tetris piece to be an (x, y) location and a rotation (t). The configuration of a Tetris piece is therefore three dimensional. We can ...


2

I am assuming that your problem is: Assume the placement location is known. How do I find the optimal sequence of moves to put the piece in the correct location? One answer to this question is to interpret the problem as an Action Planning problem. The simplest algorithm to solve it is probably STRIPS. There is another algorithm that is a more ...


0

I would store the data in a graph to help with pathfinding - nodes are intersections and edges are streets (with one-way, no pedestrian, etc flags). Then for storing the data I would take a multi-layered approach Gather the Source Data First find some way to define (or import) the data. Likely a visual tool would help, but you could get away with something ...


0

Sounds like you want a graph data type. Nodes could store their positions, plus references to features like restaurants, as well as references to other graph nodes. This is effectively an adjacency list. Existing pathfinding algorithms work well on such graphs. You could easily calculate the weight of a graph edge (the "difficulty" of that link) as the ...


0

when I click an impassable tile, the algorithm apparently goes through the entire map to find a route to the impassable tile — even if I'm standing next to it. Other answers are great, but I have to point at the obvious - You should not run the pathfinding to an impassable tile at all. This should be an early exit from the algo: if not IsPassable(A) ...


0

If the areas that the player are connected (no teleports etc.) and the unreachable areas are generally not very well connected, you can simply do the A* starting from the node you want to reach. That way you can still find any possible route to the destination and A* will stop searching quickly for unreachable areas.


0

To check for the longest distance in a graph between two nodes: (assuming all edges have the same weight) Run BFS from any vertex v. Use the results to select a vertex furthest away from v, we'll call it d. Run BFS from u. Find the vertex furthest away from u,we'll call it w. The distance between u and w is the longest distance in the graph. Proof: ...


3

Use multiple algorithms with different characteristics A* has some fine characteristics. In particular, it always finds the shortest path, if one exist. Unfortunately, you have found some bad characteristics as well. In this case, it must exhaustively search for all possible paths before admitting no solution exists. The "flaw" you are discovering in A* ...


0

Do the path-finding backwards. If only your map doesn't have big continuous areas of unreachable tiles then this will work. Rather than searching the entire reachable map, the path-finding will only search the enclosed unreachable area.


11

Assuming the issue is the destination is unreachable. And that the navigation mesh isn't dynamic. The easiest way to do this is have a much sparser navigation graph (sparse enough that a full run through is relatively quick) and only use the detailed graph if the pathing is possible.


1

How can I make A* more quickly conclude that a node is impassable? Profile your Node.IsPassable() function, figure out the slowest parts, speed them up. When deciding whether a node is passable, put the most likely situations at the top, so that most of the time the function returns right away without bothering to check the more obscure possibilities. ...


2

Some more ideas in addition to the answers above: Cache results of A* search. Save the path data from cell A to cell B and reuse if possible. This is more applicable in static maps and you will have to do more work with dynamic maps. Cache the neighbours of each cell. A* implementation need to expand each node and add its neighbours to the open set to ...


1

If your map is static you can just have each separate section have there own code and check this first before running A*. This can be done upon map creation or even coded in the map. Impassable tiles should have a flag and when moving to a tile like that you could opt not to run A* or pick a tile next to it that is reachable. If you have dynamic maps ...



Top 50 recent answers are included