# pithlit

Member

48

179 Neutral

• Rank
Member
1. ## Understanding the Jump Point Search algorithm

Hi Markk, Consider what would happen if the blue nodes were not jump points: you would continue to recurse diagonally away from the current node and miss a potential turn of the optimal path. To avoid this problem JPS only recurses diagonally if it determines there are no jump points in a vertical or horizontal direction. If it finds such a node, the recursion stops and the current node returned as a jump point.
2. ## What heuristic should i use for A* ?

[quote name='Jarod42' timestamp='1320069928' post='4878889'] The better is your heuristic, the less node you may expect to visit. [/quote] Correct. For grids, Manhattan distance is OK if diagonal moves are not allowed. Otherwise, I'd use Octile Distance. [quote]An other thing with heuristic is how it breaks tie which can favour some (equivalent) path from other. Euclidean Distance will favour path along the straight line. [/quote] I don't see how. Unless you program A* to break ties in favour of the path with the fewest turns? At any rate, this isn't a good approach. Normally ties should be broken in favour of the node with the larger g value. Otherwise A* can expand an awful lot of extra states. See Figure 1 in this [url="https://harablog.wordpress.com/2011/08/26/fast-pathfinding-via-symmetry-breaking/"]article[/url] for an example.
3. ## Genetic Algorithms for TSP

[quote name='Franck Dernoncourt' timestamp='1318406659' post='4871766'] [size="2"][color=#1C2837]So crossovers turned out to be useful and diversity is used in the fitness function in order to avoid premature convergence (=[i] genetic drift[/i] in GA terminology), such as illustrated below:[/color][/size] [size="2"][color="#1c2837"][/color][/size][/quote] I think the GA is just used as a diversification mechanism here: an alternative meta-heuristic that picks new neighbourhoods to search in. IIRC the local search itself is using an exchange operator that ranks edges based on how close they are to being part of the Minimum Spanning Tree of all cities.
4. ## How to keep the pathfinder in lane

Flow Annotations sound like what you're looking for. Take a look at Wang and Botea's "Fast and Efficient Multi-Agent Pathfinding" paper from ICAPS 2008.
5. ## Best way to "shrink" a navigation mesh to account for npc radius

Your approach sound reasonable: just annotate the edges with some clearance information to help the pathfinder. You may also want to look at Douglas Demyen's TRA* article; I believe it solves a similar problem to yours. Google for it, I'm sure you'll find it easily. What's wrong with the Minkowski approach btw? You do it once as a pre-processing step so it shouldn't matter if it takes some time? Thomas Young had a nice article on implementing this sort of thing in Game Programming Gems 2. It was called "Expanded Geometry for Points-of-Visibility Pathfinding". Maybe look at that. iirc: he simply drags the collision shape of the agent around the mesh of each obstacle in order to expand its bounding volume. I think this is much faster than calculating a proper Minkowski sum.
6. ## Genetic Algorithms for TSP

GAs are terrible local search solvers for TSPs. State of the art solvers use hand-crafted meta-heuristics to direct the search toward promising solutions. These are usually combined with some kind of edge-swapping move operator like Lin-Kernighan or Stem-and-Cycle. Check out [url="http://www.akira.ruc.dk/~keld/research/LKH/"]LKH[/url] for example; winner of the DIMACS challenge for TSPs.
7. ## A* - Which Cell Size?

[quote name='P@u1' timestamp='1317135040' post='4866461'] This probably can solve some of my pathfinding problems. I really like to do it with a grid, because it makes things very simple. I think that unfortunately this will only work out with quadratic units, won't it? [/quote] It will work as long as you use a square bounding box for your units. This constraint is similar to the circular bounding box constraint required by navigation meshes. You could probably use the annotated clearance values to reason about other types of bounding boxes (like rectangles) but you now need to figure out if there is enough room for the unit to turn and rotate. The article doesn't deal with that extension so the hard work is up to you ;) [quote]And how would you implement collision avoidance on top of this? I think of something like before examining any node with A* I check if a move to this node would yield a collision with a not-moving unit and if so, the cell/node is treated as unpassable. Later when the path is executed the same checks are made before entering any node/cell. [/quote] You could use something like temporal reservations (see David Silver's 2005 article entitled Cooperative Pathfinding). The current state of the art has moved on a bit since then however: techniques like MAPP (see Wang and Botea 2009, 2011) scale better and (iirc) have lower memory requirements.
8. ## A* - Which Cell Size?

[quote name='ApochPiQ' timestamp='1316912178' post='4865618'] You have two basic options. One is to build a [i]waypoint graph[/i] as has been described; each node in your A* graph ([b]not [/b]a grid) carries a radius that describes how large of a unit can pass through that node. Adjusting the A* algorithm to search only nodes with a minimum radius is trivial. The other is to build a [i]navigation mesh[/i] where you use polygons to represent pathable areas, select a sequence of polygons to travel across using A*, then use something like a local steering algorithm to actually move across each individual polygon. [/quote] Grid-based approaches can work [url="http://aigamedev.com/open/tutorials/clearance-based-pathfinding/"]just as well[/url] They're simple to implement, don't suffer from high branching factor issues (like waypoints) and there's no need for local steering (like nav meshes). OTOH, you probably need to smooth the paths; using either post-processing or online via Any-angle A*.
9. ## Fast Pathfinding via Symmetry Breaking

[quote name='noisecrime' timestamp='1315532420' post='4859317'] Yeah I read that 'Uniform-cost grid' bit, just wanted to double check. As I said I like the idea, it seems straightforward and offers obvious benefits, hopefully providing a spring board to variable cost cells. [/quote] If you assign variable costs to cells, rather than edges, the above suggestion *should* work; but until I get a chance to figure out if the proof of optimality still holds, I make no theoretical guarantees
10. ## Fast Pathfinding via Symmetry Breaking

[quote name='noisecrime' timestamp='1315510430' post='4859184'] Interesting read, I like the basic concept. I've only quickly skimmed through it and not looked at the paper at all, but is this limited to dealing with pathfinding on grids where cells are either passable or not (i.e boolean checks)? If so doesn't that tend to limit there usefulness? [/quote] The method is specific to uniform-cost grids. That means that all tiles are either traversable or not and the cost of moving from one traversable tile to another is fixed (i.e. 1 for straight steps, sqrt(2) for diagonals). This is a common enough domain that I don't regard specialising for it as a weakness. But yes, it does reduce the applicability of the technique. Having said that: you could apply a simple variation of this method to some weighted grids. For example: use A* + JPS to pathfind across uniform cost regions and stop recursing when you encounter a node with a neighbour in a different-cost region. This simple approach will, I think, work nicely if you have a map with a few large uniform cost areas -- which is usually the case in an RTS for example. I haven't sat down to and tried to prove optimality but off the top of my head, it seems like it should work.
11. ## Fast Pathfinding via Symmetry Breaking

The [url="http://harablog.wordpress.com/2011/09/07/jump-point-search/"]third[/url] and final part of this series is now up. In it I outline Jump Point Search: a combination of two really simple neighbour pruning rules that, together, can speed up optimal pathfinding on grid maps by up to 30 times. In addition to being very fast, this method is applied online, requires no pre-processing and has zero memory overhead.
12. ## Fast Pathfinding via Symmetry Breaking

[url="http://harablog.wordpress.com/2011/09/01/rectangular-symmetry-reduction/"]Part 2[/url] of this series is now up. In it, I describe how using a simple empty rectangle decomposition can sometimes quite dramatically speed up pathfinding on uniform-cost grids.
13. ## Pathing using Avoidance

Let me see if I have this right: you define a bounding circle around your unit and then you sample points along its perimeter, ultimately choosing the point heuristically closest to the target for the placement of the next bounding circle. You then repeat until you have a point whose bounding circle contains the target. Assuming I haven't butchered your idea too much with the above summary, I have a couple of questions. 1. It's unclear to me if your algorithm is complete; i.e. are you guaranteed to find a path if one exists? For example, does your method systematically recurse to consider all possible paths in the event that a direct path doesn't exist? 2. You claim this approach supports dynamic environments. What happens when a change to the environment invalidates your path. Do you re-plan from scratch? More generally: why do you need to compute the search graph every time? Why not pre-process your map to build a graph of avoidance circles and simply repair it locally when there is a change to the environment. This approach will not only scale much better (longer paths, more units etc) but you will be able to create some kind of hierarchy on top of it to further speed up your pathfinding.
14. ## Fast Pathfinding via Symmetry Breaking

[quote name='ApochPiQ' timestamp='1314512558' post='4854654'] In any case, it's something that hierarchical searches have historically solved well for me personally. A good hierarchical implementation of A* sounds like a combo of the two techniques you mentioned, with perhaps a stronger emphasis on what effectively amounts to caching commonly used sequences of nodes into higher-level graphs. I've seen both automatic precomputation and manual design methods for doing this; depends on the data set really. I'll readily admit that my experience is more informed by pragmatics and experimentation than actual academic research, though :-)[/quote] Hierarchical search is very nice (not to mention fast) but it is usually suboptimal and the returned solutions usually need to be refined. The two methods I discuss in the article are, by comparison, always grid-optimal and require no refinement search. Furthermore, you can easily combine both RSR and JPS with hierarchical search or some other existing optimisation technique. For example: compute an abstract graph by dividing the map into neighbourhoods. Then, compute an abstract path for some arbitrary instance. Later, when you need to refine the abstract path, use JPS to speed up each neighbourhood crossing. [quote]Anyways... I think it's an interesting concept although I unfortunately lack the time to dig into the actual methodology for myself. Definitely keep us posted when you get to working on arbitrary-cost grids and even arbitrary-shaped graphs; I'd love to see it! [/quote] I have some ideas here but nothing worth writing about yet. I'll keep you posted though ;)
15. ## Fast Pathfinding via Symmetry Breaking

[quote name='ApochPiQ' timestamp='1314374631' post='4854106'] Can you give more examples of the case where A* expands too many redundant nodes? The last time I had a serious problem with overexploration was actually a bug in my A* implementation; generally if heuristics are good I personally have seen pretty well-focused searches. It may just be a characteristic of the kind of graphs I've been working on, though (arbitrary 3-space waypoint graphs versus 2-space uniform-weighted grids).[/quote] It's easy to make up such problems. Simply pick a start and goal that requires the optimal path to go around an obstacle or around a cul-de-sac which lies in the same direction as the goal. In these cases simple heuristic functions like Manhattan Distance or Euclidean Distance severely under-estimate the cost-to-go and you end up with many nodes that appear promising but which are worthless. On a grid this problem is further compounded by the fact that each of these nodes is usually reachable by many symmetric path segments. Infact, the larger the local area that must be crossed, the more symmetry it contains. [quote]I'd be very curious to hear how your techniques generalize to graph search problems versus just uniform-grid search problems, as A* is a much more general algorithm than just path-finding on a 2D uniform plane. [/quote] It is unclear to me if simple pruning operators like RSR and JPS generalise to arbitrary problem graphs. It might be possible to pre-process the search space and identify symmetric regions but I do not have a strong theoretical result. Such questions are the subject of future work for my research If I were working with waypoint graphs, I might look into Contraction Hierarchies [1] or Transit Node Routing [2] as a way of reducing my search space to speed up optimal pathfinding. CHs pre-process a map and introduce "shortcut edges" that allow macro-steps to be taken during search. Transit Nodes on the other hand identify a small set of nodes that appear on a large portion of shortest paths between arbitrary nodes and store a database of exact distances between all such nodes. Also stored are exact costs between nodes in a local neighbourhood and their nearest transit nodes. You can also combine both approaches for even better results but keep in mind that in each case the best results are achieved by discarding A* in favour of Dijkstra's Algorithm. [1] R. Geisberger, P. Sanders, D. Schultes, D. Delling. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In 7th Workshop on Experimental Algorithms (WEA), LNCS 5038, pp. 319-333. © Springer, 2008. [2] H. Bast, S. Funke, P. Sanders, D. Schultes. Fast Routing in Road Networks with Transit Nodes. Science, Vol. 316. no. 5824, p. 566, 27. April 2007.