Ghost.b88

We found that in the case of a formation travelling along side a bunch of buildings, path-finding eat up a lot of CPU time. This is due to the units travelling in a formation, and the formation assigns positions for the units to move to. Unfortunately, when the formation travels along the buildings, it assigns positions that are un-reachable / un-walkable for the units, so all those units have to re-do path-finding to the impossible location. I have seen a worst case where the all the units in a formation tries to squeeze into a small gap / corridor, and because only one unit can squeeze through at a time, the ComputeShortPath can go up as far as 20msec / frame. The problem can be slightly alleviated by increasing the CHECK_TARGET_MOVEMENT_MIN_DELTA_FORMATION value from CELL_SIZE*1 to anything larger than CELL_SIZE*1, but at the sacrifice of deformation. If it is set to CELL_SIZE*2, then the performance in the worst case scenario increases by 50%, i.e. from 20msec / frame to 10ms / frame. However, the root problem is still fixing formations. Somehow assigning appropriate positions for the individual units (at least avoid the static obstacles). So far we haven't implemented any real solutions. Below is our profiler results from VTune. CheckVisibility seems to be a bottleneck within the ComputeShortPath. Function Name Timer samples Timer % Timer events allmul 4151 29.37% 4151000 CheckVisibility 1345 9.52% 1345000 isqrt64 1210 8.56% 1210000 CheckVisibilityLeft 874 6.18% 874000 pop 866 6.13% 866000 CompareLength 670 4.74% 670000 CheckVisibilityRight 591 4.18% 591000 allshr 538 3.81% 538000 ComputeShortPath 479 3.39% 479000 LosUpdateHelperIncremental 376 2.66% 376000 CheckVisibilityBottom 369 2.61% 369000 CheckVisibilityTop 282 2.00% 282000 push_back 209 1.48% 209000 _Insertion_sort1<std::_Vector_iterator<Edge,std::allocator<Edge> >,EdgeSort,Edge> 204 1.44% 204000 ProcessNeighbour 127 0.90% 127000 find 101 0.71% 101000 CalculateCostDelta 97 0.69% 97000 _Unguarded_partition<std::_Vector_iterator<Edge,std::allocator<Edge> >,EdgeSort> 93 0.66% 93000 SplitAAEdges 83 0.59% 83000

How do the edges come into play? Also, we noticed when the formation is scrambled, units try to catch up to the formation, and needs to re-calculate their path everytime, so this may lower the performance. What's worse is when units are close to their destinations but goes all the way back to their formation! We are thinking of doing a check there (if closer to destination, go to it, when close to formation, join back), not sure what the performance gain is, but it seems to make more sense this way. Also, what does the avoid moving unit flag do? Does it do anything intelligent to avoid moving units? such as waiting for few turns for the moving units to leave the position. As for unit position prediction, perhaps we can build a virtual map for future turns, and all the units who have paths established register their future positions on the virtual maps, and when it comes to path-finding, the unit checks its own future path against the virtual maps, and re-route if a future path is blocked? Also, how come the Vertex path finder may be in a situation where it ends up in a non-reachable location? Doesn't the tile path finder already assesses the possibility of path-finding?

Is there a measure of active members? I.e. Users who posted in the last week or month? Thanks for the statistics guys, I appreciate it.

For the vertices pair, why is the moving unit represented by a square instead of a point? This would make it n^2 instead of (4n)^2, wouldn't it? Also, when forming the pairs, one of the lines will always be obstructed, the point of the obstruction square that's furthest away from the moving unit. Perhaps this can be an optimization?

But what about the game install folder? Surely you'd be able to write files there since you installed the game there. How many people have joined the 0 A.D. Forum? Thank you for the stats, this gives me a better sense of the developer activIty and user base, which is required for my assignment.

What does axis-aligned mean? I.e. AA edges and squares? What makes the vertex path finding so slow? Doesn't it also use A* algorithm? And Can someone describe the formation system a little bit further? Also, how is the collision detection and avoidance set up? Currently I am noticing a large amount of A* path finding when a group of units travel along the buildings in pathfinding demo map. I noticed when collision occurs, most of the units panic and start a new path finding, driving up the computershortestpath time. I read the article written by the former aoe developer on path finding, and he briefly talked about formation and group path finding, so I'm wondering how that is handled currently. In addition, the article also brought up the idea of predicting paths, so that collisions can be avoided in the future. Any comment of the feasibility ofthis method? And can anyone think of better methods for collision detection and avoidance?

Thank you. Just out of curiosity, why do games like to put data into the user profile's application data? Also I'd like to know the approximate numbers of developers are in on this project, and the approximate number of user base, please and thanks in advance.

Thank you for the explanation, I have a better understanding of how this path-finding works now.

How come some components are circled in green? And send my regards for the person who created this, it's quite impressive!

Thanks. This will help me understand what the game is doing.

Is there a way to save a replay of a game and replay later? The idea is that we can use the same scenario to test the pre-optimized code and optimized code, and see if an improvement is made.

Hi Ykkrosh, where is the logs folder you were referring to? It's suppose to have sim_log/$PID/commands.txt? And the replay takes that text file? This is probably not the most appropriate place to ask these technical questions, sorry.

What is the current status of the path-finding component? Are all of the path-finding algorithm found in AOM implemented? Has caching paths been implemented?

What profiler does the game currently use? And how is it getting the resolution of the measurements down to usecs?

Hi, I looked around at the site and source code a bit yesterday, and I found some really good design docs (engine documentation, AI, etc.) that describe how the game works. However, I am wondering if there is an architecture diagram of some sort, something like class diagram and sequence diagram? Something in Visio, for example. I want to see how the components / classes / objects interact with each other, and the relationships they have with each other. In addition, how do I get the debugging output or log files? anything text that describes the actions and events and errors that are happening when I am playing / profiling the game? Thanks in advance.