scroogie

Wow, considering how large that view is and how small the model will be in the game, thats really impressive, great work.

Netbeans nowadays also has support for C++ and JavaScript, including code completion and debugging support. I'm not using it for C++, but its not bad at all.

Hi Yves, once again great work on these investigations. Judging from the results of profiling, how much time is actually spent in Javascript, I'd say that this would be extremely worthy to achieve. To be honest I'd even say that 75MB more memory consumption is neglectable, I'm curious how discussions about that will proceed.

If the memory consumption was between the old and new version, that would be of no concern, would it? Even the v24 was well below 100Megs most of the time, if I don't misread your graph. Or are there many complaints about 0ad being memory hungry?

Wow, 13.5% is a really massive change. What do you mean by kind of a memory leak? Wouldn't it make sense to have all Javascript code compiled, as it doesn't change?

Well, thinking about it, as it creates collision edges for all obstructions, I'm quiet certain its related to the amount of all obstructions on the map. Maybe Ykkrosh can explain how Trees affect it specifically.

Which maps would you like to compare? Do you have specific ideads? To have "realistic" human behaviour in there, I played the game myself and used the sim_log for the profiling. You can also attach commands.txt and I run it through the profiler if you want.

I did a new profile on r15552 using a replay of a 1 human, 3 petra bot match, 20713 turns. Time spent in modules: 55.9% pyrogenesis 32.3% libmozjs (javascript) 6.3% libc 4.1% libstdc++ 0.7% libnspr4 The previously found (minor) hotspots are gone, the PathFinder appears more prominently now, but there were also a lot more units in the game. Looking at the subtree analysis, CCmpPathfinder::ProcessShortRequests() takes 46.4% and CCmpPathfinder::ProcessLongRequests() takes 15.2% (of course relative to the 55.9% spent in pyrogenesis). The only other subtree that appears prominently is BroadcastMessages Looking closer: - in BroadcastMessages the cost is mainly caused by the RangeManager (GetNear and UpdateVisibilityData) and CCmpPosition::MoveAndTurnTo (itself due to posting messages) - in ComputeShortPath, the most costly subtrees are the EdgeSort and the CheckVisibility functions (there apparently is a huge amount of edges to iterate over) - in the long range pathfinder, CalculateHeuristic and DistanceToGoal call isqrt64 awfully lot So actually, there is nothing new, except that the situation has improved imho. Apparently there are no low hanging fruit anymore. :/ I'll keep the results, in case someone is interested.

Starting here, there are a few profiles: http://www.wildfiregames.com/forum/index.php?showtopic=17274&page=6#entry270911

The thing with performance improvements is that they often only change performance by a small margin, 1% say, but if you do that in a hundred commits, it adds up. And i've often seen it working like that. You benchmark / profile, address one issue giving you 1% gain, then you benchmark/profile again, and address another hotspot, etc. But anyway, this is actually quite offtopic here. Just out of curiosity, what *are* the actual disadvantages of doing the move? I think even on LTS distributions like RHEL its no problem to install e.g. gcc 4.7 in case its required.

You can read more about issues and possible solutions in countless papers. I'd suggest these as a starter: HPA* Near-optimal Hierarchical Pathfinding: http://www.cs.ualberta.ca/~mmueller/ps/hpastar.pdf It explains the idea and implementation of long-range / short-range pathfinding. Jump-Point Search: https://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3761/4007 The algorithm that was chosen for the (incomplete) rewrite. Apparently improvements will soon be published: http://www.nicta.com.au/pub?id=7771 As mentioned in the paper, it could potentially be combined with swamps as well: http://leibniz.cs.huji.ac.il/tr/1188.pdf Another approach that seems to be getting a lot of attention is SUB: http://idm-lab.org/bib/abstracts/papers/icaps13.pdf

Hi Yves, let me say thanks for your tremendous effort on this, its always a pleasure to read about your progress! KeepJitCode was the one where Jit code is not garbage collected, right? Do the Mozilla Devs plan to make this safe in ESR31? I honestly don't know how this could work with a moving GC? @FeXoR: To the contrary, all ESR31 versions are actually faster. And quite substantially as well (biggest improvement seems to be around 18% by visual judgement).

I've also posted some profiles/traces on another thread if more info is required. Regarding the isqrt, if I remember correctly the new pathfinder patch drastically reduced the number of calls there. Afaik the current one still uses vector lengths which obviously requires a lot of sqrts.

If I may say so as an outsider, I think the buildings look fantastic, you Art guys are really doing a splendid job. Whats described as "cartoonish" here could perhaps really be the colors / contrast / saturation. Maybe some of the textures are too perfect and could use some muckiness, and others could get toned down a bit. But I really think it looks great. You certainly know better than me, just my 2cts.

Wow, these are really great. The run animation also seems to be very realistic, comparing to what is found on youtube, e.g. Although in that fast run for hunting, everything is a bit more emphasised, which makes it look more powerful, e.g. the hind legs seem to jump further to the front, and there is a larger muscle movement. Nevertheless, I think the level of detail is already great. Btw, its amazing to see how this comes together. The art section is really a pleasure to watch. You are all doing a great work.

Just out of curiosity. Is 512 the max amount of tiles? How large (in meters) is a unit in comparison?

Great to see that you are actually investigating this. Perhaps, as other people have repeatedly tried to look into this, you could preserve somewhere how you investigated / tested solutions. Are you replacing both the short-range and long-range pathfinder, or one of them?

So I'm a bit confused now. I guess entities have an extent, but the RangeManager ignores it (which is what I meant to ask)? Does the range vary very much or is it quite uniform? Ah, yes, I didn't see the static initialization. I'm still not sure its nicer than using OpenMP, though. The latter would also allow tasks (if 3.0 would be an option), which might even be better suited sometimes. But anyhow, I would still tend to the component-wise solution. Yes. Regarding the issue of waiting for the results, its virtually a decision between blocking the whole game to wait for a result or live with an old result for some time? Also, you gain some time in a way, which is currently unused because of the sequential processing. If we take the AI again as an example, it could already crunch away while the engine is busy with other stuff. Its in no way trivial, but I guess maintaining a bunch of parallel sections isn't trivial in the long run either? Anyway, I digress. I hope you don't mind if "externals" chime in, its an interesting topic.

Hi RedFox, sorry I don't remember, does the RangeManager treat entities as points or as featuring some radius? *edit* I just had a look at the parallel for patch. Don't you think that is a quite painful way of doing multithreading in games? First, I'd assume it would be easier to use some existing implementation with threadpools etc., like even OpenMP. Secondly, I'd think the easiest (and most common afaik) way of doing it is completely putting one component in a seperate thread, like the AI. That way you don't need to make sure that every called method is threadsafe etc., which will be horrible to maintain over time, at least in my experience.

Hi RedFox, this is what I meant with the cost of getting items in exactly the state you need for SP, but so be it. I'm quite sure your work was still valuable! For example your testbed implementations. Could that code be used by others that want to experiment with the RangeManager? E.g. did you isolate parts so that debugging or performance measurement is easier? I guess that would already help very much. Cheers

Just to add to the good explanations of sanderd, if you look at the short range pathfinder, it is basically a points-of-visibility algorithm with high precision obstruction edges connecting corners. I think there was also an article in a GPG issue that explained PoV pathfinding. Maybe it helps to understand the idea behind it. Apart from the mismatches of the two systems, the problem seems to be that it is simply too expensive. I don't know how good a NavMesh approach will fare, especially because of the modifications of the obstructions, online replanning, and unit clearance (i.e. point 3), but its definitely worth a try. I assume you'd need some additional subdivision to floodfill (or however you build the navmesh) only parts of the map.

Yes, I know, but what does this change? A sweep is basically the most trivial algorithm one can come up with. Its just traversing all items in the way you keep them. The more interesting question is how to get them to this state, and thats where other algorithms get into the equation. Do you always sort all items, or do you keep them in groups, etc. Im afraid thats what all algorithmic geometry is about.

With that argument, you don't need any algorithm at all. It all depends on the situation. Sometimes its about the need to sort or not.

I don't think that using a simple Sweep is a real answer to everything. It can be faster, but so can KD-Tree, RB-trees, QuadTrees, etc. pp. I liked the idea of kuranes, to first fix an abstract API of spatial partitioning, and then implement different techniques to see how they fare against each other in different situations.

jcantero: I think this was discussed several times. I would have chosen Lua as well, but apparently there were reasons against it. Just saying that people were actually aware of Lua.