Jump to content


Community Members
  • Posts

  • Joined

  • Last visited

  • Days Won


Posts posted by scroogie

  1. Yes, I was quite surprised to see the amount of time the JavaScript takes, I mean, the fully inclusive usage. I guess it impressively shows how much is really done in JavaScript. More than I thought, but I never really looked at the AIs. From the module classification in VTune, you see that 44.8% (!!) of the time is spent in libmozjs as compared to pyrogenesis.

    I'd also think that ExecuteActiveQueries is the most sensible target right now.

  2. So, to add to this, from the list in the prior post:

    - GetPercentMapExplored has a patch in trac.

    - isqrt64 is not debatable. Maybe the game can save on normalisations and length calls (and there are already some patches that do), but I think thats for long-term.

    - GetInRange can probably profit from the work on a Quadtree.

    - which will also help PerformQuery. That also uses a sorted list of entities, but still traverses all of them every time. Just as a sidenote, PerformQuery actually has 11.04% inclusive time in my measurements, so its really relevant. Nearly 40% of this time is spent on finding entities by id.

    - CalculateTerritories could maybe be changed to only recompute parts of the influence map on changes, instead of recomputing the whole map?

    - LosUpdateHelperIncremental could maybe use LOS templates, like in the GPG article? This would also offer easy flexibility on vision ranges (instead of just circles).

    - As said above the RangeManager in general does a lot of map finds for entity ids, which can be replaced with the entity container that is being worked on in trac.

    CCmpPathfinder_Tile::ProcessNeighbour() and CCmpPathfinder_Vertex::SplitAAEdges() are different stories, still curious what tuan comes up with. :)

  3. The implementation is nice, but I think its not optimal to judge it by just looking at the code. Maybe it would be good to have a patch that actually demonstrates it. For example, CCmpRangeManager would be a good place to start, as it uses a struct EntityData, which maps nicely to your game object idea. It currently uses SpatialSubdivision, so you could easily compare it and even do benchmarks. This also shows some conventions which could maybe influence the Quadtree class, like using entity_pos_t, having a way of updating the subdivision on Motion Events and so on.

    tuan_kuranes also had the idea to have a common base interface for different spatial subdivision approaches. I think that sounds like a nice idea, and shouldn't be too hard to achieve.

  4. I've run a full 1on1 game against Aegis on Acropolis 3 through callgrind (10383 turns) to get an overview of the performance. I know its not accurate, but I think it gives valid pointers. If anyone is interested, I can upload the output data.

    There are some interesting things in the output. As expected, the most costly function is CCmpPathfinder::ComputeShortPath(). Out of the 100 functions with the largest self cost, more than 50% are inside libmozjs (e.g. EnumerateNativeProperties, js_AtomizeString, Snapshot, str_split, js::EqualStrings, js_TraceObject, etc.), so I guess that shows the importance of the Spidermonkey upgrades / performance work currently done. Other functions showing high self cost are (in order) GetPercentMapExplored, map::find, isqrt64, SpatialSubdivision::GetInRange(), CCmpTerritorryManager::CalculateTerritories(), CCmpRangeManager::PerformQuery(), Pathfinder_Tile::ProcessNeighbour(), CCmpRangeManager::LosUpdateHelperIncremental and CCmpPathFinder_Vertex::SplitAAEdges().

  5. I've ran a full game (10383 turns) against a bot on Acropolis 3 through callgrind, as I was curious about the hotspots of the game. It counted 75 196 964 calls to malloc, if that is of any interest. Its actually number 6 on the most-called function list. Even more impressive is std::_Rb_tree<unsigned int const, EntityData>::find(unsigned int const&), which was called 183283748 times. There are some other interesting results, like GetPercentMapExplored taking 6.56%, but I guess thats totally offtopic here.

  6. Most people won't end up using fancy translation software, but in the case they want to, we'll have the PO Template for them and the tool that convert it back to .txt.

    I've never worked on commercial games, but on a few open source projects, and my experience is that the biggest advantage of gettext is actually that the tools are so dead easy. Lokalize (http://userbase.kde.org/Lokalize), Poedit (http://www.poedit.net/screenshots.php) etc. are very accessible and easily learned. I wouldn't call them fancy. Then there are the ready-to-use webinterface for hosted translation systems, e.g. Pootle and Weblate. Just to get an impression for people that don't know them (random links into demo projects):



    These interfaces can be integrated with all popular VCS (git, svn, cvs at least) so you can work on trunk, branches, etc. and directly commit from the interface.

    In my opinion the emphasis is quite naturally a bit different for open source projects than for commercial projects, as for open source projects the translators need to be attracted and motivated first, which is probably the most important aspect then.

    Please note this is not an argument against using an additional intermediate layer for more efficient in-game usage. I just wanted to point out that the tools can make a massive difference.


  7. I don't feel strongly either way about quad- versus octree. There's a strong efficiency argument for the quadtree, and there's a strong argument that an octree will allow us more realistic 3d modeling of the game world. I, for one, want to be able to fire arrows down from a highway overpass as my enemy marches underneath, but that probably won't happen any time soon. Perhaps I'll add a compile-time flag that turns the third dimension on and off, so my code is still useful after the argument is decided.

    This is a misconception that I tried to clarify in the other thread. Using a Quadtree absolutely does not rule out stuff as this. You can have units flying as high as you want with Quadtrees, even having thousands of units on top of each other. It just won't give you the same speedup for the Z axis. Using a Quad/Octree does not mean that you do not compare locations at all any more. It just means that you compare much less positions, as you can rule out the majority through the subdivison (you know they are not close enough). With only a quadtree, you'd have to compare all unit positions of units that are above each other, while with an octree you save most of the comparisons due to the subdivision.

    About the implementation, I'd just start with a loose quadtree as described in GPG, with just the basic methods, and then as people figure out where and how to use it, more will be added later.

  8. I just recompiled. All music plays well, also the battle music, but the error message persists, everytime a new track is played.

    Since today, I also receive many many many of the following messages:

    WARNING: OpenAL: stereo sounds can't be positioned: audio/actor/human/death/death_13.ogg

    WARNING: OpenAL: stereo sounds can't be positioned: audio/interface/select/building/sel_barracks.ogg

    WARNING: OpenAL: stereo sounds can't be positioned: audio/voice/hellenes/civ/female/civ_female_march_2.ogg

    etc. pp.

  9. I think the intuitive high performance of the above idea gets it's apparent usefulness from a better, more generalized high level pathfinding concept. "Successive Approximation". Basically, any such algo that only computes a fast, coarse, approximate path to follow, which gets more and more precise the more times it is iterated, would be a "successive approximation" approach. The idea being, you will have plenty of time to do computations so long as it takes time for your units to actually get from A to B. And during travel, you don't necessarily need an exact path to follow. Though as demonstrated above, there are cases where the best path needs counter-intuitive movements right at the start.

    This is how it should work already. At least if the U-Shape you describe would be a static obstruction (buildings, territory, water, ...). The pathfinder does a rough cell-based approximation which is quick, and computes a list of rough waypoints to follow along this path. The short-range pathfinder is only used to compute the way from one waypoint to the next one.

    It is NOT a trivial A* implementation which starts walking along incomplete paths. It starts along a complete but rough path, and then does interpolation, dynamic obstacle (units) avoidance, and so on.

  10. As far as I remember the path computation is async. The unit starts moving in the direction of the next rough waypoint (Pathfinder_Tile) which is quick, and then asynchronously computes the short range path, which takes longer, but doesn't block the frame. At least this is how I understood it, correct me if I'm wrong.

  11. The short range pathfinder is a points of visibility with quite exact visibility edges, so the result should actually be very good. I think the problem is that its too slow. This is also shown in the behavior that is reported here, that single units can get out of the forests easily (and find paths through very small gaps between walls and cliffs btw). The problem is probably the way the groups are handled. Of course, the long range and short range pathfinder not agreeing with each other, due to the size of cells is a problem (described here as well, the unit starting and then stopping in front of the clearance).

    Btw. I'd love to have Wall "snapping" behavior at obstructed terrain, closing gaps. I also like doing that.

  12. I wouldn't rule it out. If it's not too expensive (I'm speaking CPU-wise here), we could use it to have better frustrum cullings (such as removing bushes that can't be seen but not big trees or something). It would probably need to be slightly clever, though. And it'd indeed be nice to have. But if it leads to a somewhat significant slowdown, then scrap it.

    It is actually quite expensive. How is frustum culling done currently? I don't really see how you subdividing the third dimension helps there, but maybe I miss it. To rephrase what RedFox said, subdividing along an Axis in my opinion only makes sense if there is so much variation on that axis, that you actually seperate a lot of objects. In the case of 0ad its most probably much cheaper to test all objects that are above each other than to subdivide it. Especially if you want to use a uniform scheme. I'd imagine that you'd either have too many empty cells or the smaller vertical extent will ruin your horizontal subdivision (of course there are ways around that, but it'll add complexity again).

  13. I'm still not convinced that the game actually needs an Octree instead of a Quadtree. I feel even with flying units, the subdivision in the Z axis would be unnecessary, but others are much more knowledgeable than me.

    I just wanted to point out that there is already an abstraction for spatial subdivisions here: http://trac.wildfiregames.com/browser/ps/trunk/source/simulation2/helpers/Spatial.h

    But I don't know if its used everywhere. Probably the hardest part will be to look at RangeManager, ObstructionManager, Terrain, Territory etc. to see where it could be applied. Because of the amount of units it might be helpful to take a look at loose quadtrees.

  • Create New...