New answers tagged path-finding
0
The A-* algorithm requires hat the set of possible agent locations be discrete, not continuous, and that there be a connectivity relation between the set of possible locations, called nodes.
A well-written A_* algorithm will not require any particular storage choice for the nodes and the connectivity, but will use Inversion of Control to obtain the ...
6
when should i use BFS instead of Dijkstra's Method
BFS applies to unweighted graphs only. Dijksta's is just an extension of BFS to weighted graphs - Dijksta's on an unweighted graph will examine exactly the same nodes as BFS.
So, they can essentially be viewed as the same algorithm.
Or is A* an answer to all the prayers and there is no reason not ...
5
You don't need to use a grid, you can easily extract node information from the roads (or keep it when placing roads). Path finding only cares about connectivity. Once you get to one node, which nodes can you go to next?
Red dots are nodes in your path finding algorithm. The orange lines define their conectivity.
The Green agent wants to go from its ...
0
I guess you mixed up "path finding" and "object state" (e.g. position, speed, direction, ..). Path finding is used to find a path from position A to position B. As far as I understand, the "Mesh based" algorithm is only used to simplify this "path finding" process, when an actor (e.g. a car) wants to move from position A to position B to reduce the maps ...
1
Actually, if you look at the definition of 45-degree route, it is always possible to transform a path with 45-degree route into a path without 45-degree turn. And it's also optimal (you can easily prove it by contradiction).
So, the simplest way is to run the jump point search and then transform it into orthogonal route.
0
You can actually do this without A*. I did this on a hex grid using recursion but the premise is the same.
You start at your characters current position with the set number of moves. then move outward in all directions reducing the number of moves by the amount of moves required to enter that square. Then repeat for each square you entered.
One thing to ...
2
A* is for finding the shortest path from vert a to vert b. Its not a good fit for finding all verts x distance from vert a.
A Depth First Search (DFS) should be suitable for your problem and very cheep on both memory and clock cycles. There is another basic search algorithm called the Breadth First Search (BFS) that would run at similar speeds but uses ...
4
In light of your question's context, http://nodewar.com/, there are a couple specific considerations for your solution:
You have a (low) maximum angular velocity, and enough maximum torque to reach it in very short time.
Your drone and target each have velocity and external acceleration unrelated to thrust (gravitation abounds).
Your desired target changes ...
3
A similar question, with some good answers, including the apparent name of this whole subject, "motion planning":
http://stackoverflow.com/questions/2560817/2d-trajectory-planning-of-a-spaceship-with-physics
As a programmer, I like the practicality of user470365's suggestion. However, I'll take a stab at a more rigorous approach. My suggestion here computes ...
3
Many game AI implementations in that situation will choose to cheat, and give themselves full knowledge of the map, where their human opponent doesn't have that. You can then simply apply A* to the full map.
How sensible this looks for computer controlled units will depend on things like how maze like the maps are, and if the player is likely to learn the ...
17
You should use the D* algorithm, which is designed for this exact scenario. Specifically, the D* Lite implementation is the most efficient and simple variant.
1
In road network it is better to have cost in edges, not in nodes.
When I was doing road networks (for navigation, not for games) related programming, I used Node that contained set of incoming and outgoing edges (and other data) and edge with both ends, reference to edge in oposite direction and again, other data.
Some of this you will probubly not need ...
Top 50 recent answers are included
