Jump to content

Kay

Community Members
  • Posts

    5
  • Joined

  • Last visited

Kay's Achievements

Tiro

Tiro (1/14)

4

Reputation

  1. Ouch, looked at CmpRangeManager again and I indeed stepped on a small landmine there regarding the "no calling code actually cares about the ID's being sorted" part. That raises a few questions though: [edit: just realized this is all purely an overhead limitation strategy] 1) Does any game logic really *need* to know which entities entered or left range since the last turn? e.g. if I am a static defense turret, do I care specifically about new enemies that walked *into* my firing range when I can just call GetInRange again and grab all the ones that are in range *now* at much smaller cost? (depending on tile size and object count, but currently the sort's form a clear bottleneck) 2) Is ExecuteActiveQueries a frequent or infrequent (conditional) callee? If it's not an oft-visited code path, then inserting std::sort's before the std::set_difference's would fix its needs and still grant the common case performance improvement, otherwise the benefit of not having to sort at all obviously goes out the window. Could this be refactored such that it would only need to be invoked optionally by parties wanting to know exact diffsets? With my patch (or wraitii's) there would be no more duplicate ID's per individual query (two or more queries overlapping in area might still contain duplicates, of course), though this comment makes me more inclined to think 0AD's default grid resolution is too coarse since a simple Euclidean distance (or w/e) out-of-range check shouldn't break the bank but sending thousands of unfiltered entities to JS per turn certainly would (especially if the overhead isn't carefully managed by sending data across in batches) and from that perspective those set_diff's are understandable. Have you guys tried experimenting with this? Spring splits objects into separate classes (trees/rocks/etc are map features, ie. specialized entities) so queries don't have to iterate over anything the caller (engine or script) does not indicate it is interested in. There's no diplomacy aspect involved, but I'm assuming that it probably doesn't make much sense for a unit to wait by default for trees or rocks to venture into its range in 0AD's world either... and from what I've seen of your maps they tend to be densely packed with them so selection at the gates wouldn't hurt.
  2. No problem, and I'll leave it at v3 then (see first post) for easier comparison. Good luck with your project.
  3. I am naturally biased toward my own patch, but SpatialQueryArray having a fixed size would be trivial to fix: just replace items[MAX_COUNT] by a std::vector (reserve()'d to some initial size) and modify copy_items accordingly. If desired I can provide a v3.diff implementing that change as well. While I am obviously unfamiliar with common 0AD development practices and don't want to take anything away from the work in 2430, a months-old unapplied patch lying around for an (apparently?) long-standing major problem suggests it contains an uncomfortable level of complexity (or perhaps simple indecisiveness ) and this is an area where KISS is paramount.
  4. Ah, seems I'm too used to Spring's conventions. Spatial.h doesn't know the definition of entity_id_t (and treats id's as uint32_t's itself), so I did that for consistency and to avoid pulling in another header. Done and re-attached: 0AD-SpatialSubdivisionPerfPatch-v2.diff (I'll create a trac account for any future patches, right now this is a side-interest)
  5. Hi, Spring engine developer here peeking over the garden walls to a fellow RTS project. While profiling 0AD I noticed certain functions relying on SpatialSubdivision::Get{Near,InRange} showed up alarmingly often and consumed much more CPU than seemed justified from the functionality provided by them. After quickly diving into your codebase I discovered that SpatialSubdivision::GetInRange calls make_unique on its SpatialQueryArray argument, which in turn issues a std::sort followed by a std::unique (!) just to handle the problem of buildings spanning multiple subdivision tiles. This is an *extremely* heavy-handed way to avoid duplicate entity ID's, not to mention a textbook case on how to kill performance since spatial queries are one of the most frequently executed (certainly in Spring's case) and hence time-critical parts of any RTS engine. So I fixed it, following the old adage that 99% of computing is an exercise in caching: 0AD-SpatialSubdivisionPerfPatch-v3.diff This trades O(n log n) time for O(n) space which I would consider an acceptable deal since space is generally cheap but time almost never is. However, it also introduces a bit of double bookkeeping in SpatialSubdivision, which may not be to everyone's taste. Either way, with these changes the relevant functions dropped to neglible percentages, so I'm calling it an hour well spent. (AFAICS no calling code actually cares about the ID's being sorted, nor should it) This patch was created against commit d14b8363fcd143d43a4888e7126e97fddf0015ab of your git mirror (sorry, not touching svn with a ten-foot pole), and is small enough that it shouldn't present any difficulty to apply. ps: if there's still a need, I might also be tempted to take a look at your pathfinder issues... for a price
×
×
  • Create New...