# Tag Info

1

The problem was this: bool AStar::Contains(std::vector<Node*> _pVector, Node* _pNode) { return find(_pVector.begin(), _pVector.end(), _pNode) != _pVector.end(); } It made a copy of the vector every single time it was called, wich made it incredibly slow. Making it a pointer to the vector increased the time from about 30 Seconds to only about 6 ...

1

EDIT: Setting it on Release mode will make the pathfinding ALMOST instant This is probably the key piece of information. Although you don't say so, your problem is presumably that you're using the STL in a debug build in something being compiled within Visual Studio. Visual Studio's implementation of the STL is notoriously (and catastrophically) slow ...

1

300 nodes in 0.03 seconds means only 10,000 nodes per second, which seems rather slow. Before implementing more complicated approaches such as hierarchical partitioning, the first thing I'd do is to optimize the code. Run the profiler to find out which functions are using the most time. It is often surprising where the time goes, and it is a waste of your ...

0

One way to implement this is to use clearance, and have all of the tiles around obstacles contain numbers represent their proximity to the object for example a map that looked like this: map = { {0,0,0,0} {0,1,1,0}, {0,1,1,0}, {0,0,0,0}, } would look like this: map = { {1,1,1,1} {1,2,2,1}, {1,2,2,1}, {1,1,1,1}, }

0

Store inside each entity not only its position, but also its size. Then you can reconstruct the collision map from your entity list, something like this: -- [ Assign 0 to everything in the map. ] -- Then block out a 1 for each square within the entity's size for _, entity in entities do local pos = entity.position for xIncrement=0,entity.size.x do ...

3

Since performance is the most important thing - I would rewrite this to use arrays rather than standard library containers. The problem with using data structures designed and developed by someone else is that if you don't understand how they're implemented you'll very easily end up performing millions of unnecessary operations - including memory allocation ...

2

Here is something that just popped into my mind: Have you seen the simulation of 3-body system? The two fighting ships can be two of the bodies, and a 3rd (invisible) body is there to create the chaos. Take a look at this video to get a feeling what it's going to look like in practice: https://www.youtube.com/watch?v=VX9IdCnNWJI Also since you are not ...

2

Is this what you want? As for finding the closest food stack, calculating the center of the swarm and using a simple A* algorithm to search all other food stack from the lowest minimum distance to the highest works, or even just a lookup table to map food stacks with their nearest neighbours (Only works if your food stacks are static and regrow). EDIT To ...

2

As you yourself have stated, you still didn't have resorted yet to optimizations. So yes, there are many ways to speed that up. But since you were talking in general terms, I will stick with what I think is the best general guidance for improving path-finding performance: decrease the size of the problem. Or in other words, search less and search smaller. ...

7

I see a few issues. you are doing a lot of linear scans over vectors (at least 2 for each neighbour for each node you examine). This will be pretty slow. You don't even need the closed set if you just have a bool isClosed in the Node. You should sort the openset or make the openSet a min heap of some description. This will make the search for the next ...

2

Create an isochrone map (https://en.wikipedia.org/wiki/Isochrone_map), get a polygon of all the points accessible within N units of time. An isochrone map basically looks like this (3 isochrones are represented in this example): Let's just focus on the red one, which takes a center point and a time (or a distance). Based on this time/distance limit, the ...

0

The A* algorithm contains a heuristic, meaning you can modify it to get a path that may not be optimal, but better suits your requirements (i.e. prefer orthogonal movement over diagonal movement). You'd modify your A* algorithm to make quick direction changes more costly. For example, if you've just changed from going down to going right, the cost of going ...

2

One possible solution, without modifying the computation or directness of the path itself (which might have unwanted effects on your gameplay), is to just tweak your logic for selecting which animation or frame to display. When the animation controller asks the movement logic which way it's moving, the movement logic can tell it a little white lie: If my ...

1

(1) Refer to the idea of an epsilon value which represents the float error range within which you are willing to accept a "success" condition. It is normal for floats to be compared using an epsilon, for example: float e = 0.0001f; //epsilon public bool FloatEquals(float a, float b) { return Math.abs(a - b) <= e; } bool Vector2Equals(Vector2 a, ...

2

I had the same problem while searching for funnel algorithm. Here it is a summarized procedure, considering one origin and target point: Triangulate your polygon Select origin and target points find origin and target triangles Do any graph search algorithm to find the path of triangles from origin to target find the path of edges connecting the triangles ...

Top 50 recent answers are included