Tag Info

Hot answers tagged

37

Some ideas on avoiding searches that result in failed paths altogether: Island ID One of the cheapest ways to effectively finish A* searches faster is to do no searches at all. If the areas are truly impassible by all agents, flood fill each area with a unique Island ID on load (or in the pipeline). When pathfinding check if the Island ID of the origin of ...


24

AStar is a complete planning algorithm, meaning if there exists a path to the node, AStar is guaranteed to find it. Consequently, it must check every path out of the start node before it can decide the goal node is unreachable. This is very undesirable when you have too many nodes. Ways to mitigate this: If you know a priori that a node is unreachable ...


17

Run a dual A* search from the target node in reverse as well at the same time in the same loop and abort both searches as soon as one is found unsolvable If the target has only 6 tiles accessible around it and the origin has 1002 tiles accessible the search will stop at 6 (dual) iterations. As soon as one search finds the other's visited nodes you can ...


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.


8

Locallity of reference does matter, but you don't have to worry that much...beucase you don't have absolute control. When using OpenGL/DirectX you usually have limited control over memory layout, the driver will do the rest. For example you can try multiple vertex buffers layouts, such as using interleaved or non-interleaved vertex data and depending on ...


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* ...


2

If the triangle strips, while being disconnected, are all sharing the same material (shaders, textures, shader constants) then you can join them together with a degenerate triangle. Since degenerate triangles have zero area they should not show up. The only case they would is if you are drawing wireframe. You make a degenerate triangle by defining the two ...


2

AFAIK standard procedure is to have resources stored in a map-like structure with strings as keys, since it's extensible as you've seen. However, for the core game elements (especially the performance-critical ones), the resources will be explicitly linked instead of involving a key-lookup, thus skipping the lookup overhead. For example, you might have a ...


2

The Chromium-based WebView causing this issue was eventually updated in KitKat version 4.4.3/4.4.4 in mid 2014, but that is cold comfort considering some vendors have made some seemingly arbitrary decisions about which of their phones got the update and which did not. Samsung Galaxy S4, for instance, is still trapped at 4.4.2. Follow the advice given by ...


2

Since there's no accepted answer I add some info, I wanted just to add things not already said by Sean in his answer. TexelFetch treat the texture as a Image, so you can access exactly the content of pixels. You usually do that when you need exactly that content, wich is in few but usefull occasions: Certain post processing filters (Guassian blur exploits ...


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

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. ...


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 ...



Only top voted, non community-wiki answers of a minimum length are eligible