CharlesS

That's pretty much what I was thinking too, or at least I was thinking this is what should be done, as it sounds more efficient.Then, the more I thought about it, the more I realized that there may be significant issues when the first most apparent path is not be even close to the correct path. For a lot of optimized paths, you may need to know the full path before you can even start moving. I mean... the most efficient path may require you move backwards at first after all. For example... Take a cup or U shape, with the unit inside the open end and the target on the other side. At first, (not having any info about the terrain), such an implementation might analyze the nearest nodes and plainly see that going straight for the target gets closest to it's goal. This remains true for several iterations of the algo right up until it hits the bottom inside of the cup/U. After that, the algo has to "look around" to get clear of the obstacle it just found. Now if this were standard A*, the unit would not have even started moving yet. The object that made it to the obstacle would only be a "phantom unit". But with the "one step at a time" algo, the actual unit has spent real travel time to get it to where it now is. And since the fastest path would clearly have been to go around the U shape from the start, and our pathfinding algo got us into the bottom, in this exact case it would be quite a poor performer, despite it's first glance usefulness. 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. The million dollar question then becomes. What kind of algorithm will do the above, and still find reasonable paths for counter-intuitive cases?

The A* section of code in CCmpPathfinder_Vertex.cpp is where all the fault lies. Running the in game profiler and playing a few games, the A* section will regularly take 100~300ms per frame to complete, and often enough it will exceed a full second of computation. The game should get at least 20 frames a second to be playable, and these numbers suggest far far far from that. I almost wonder if it's not actually a true to life bug, rather than just a slow A* implementation. Though admittedly, if it's not JPS+A*, it's going to be painfully slow even if done perfectly. Personally, I don't have a problem with a pathfinder that doesn't always find the exact perfect path, so long as it's significantly faster and usually finds the shortest path.

Hello. I just thought I would pop in to point out that assistant professor Nathan Sturtevant wrote a path finding test bet called HOG (and now HOG2) that is codded in C++ and open source. It also has a few prebaked path finding algos that might come in handy. If you like, you can pick that up here... https://code.google....source/checkout Also, if anyone would like some laypersons info on A*+JPS, there is an interesting read here... http://aigamedev.com...in-pathfinding/ Long story short, JPS and friends makes a path finding algo much faster because it quickly eliminates calculating multiple possible paths that would all have the same effective length, or at least that's what I had taken away from it. The results on that page are pretty astounding in any case. If you're not already, you should definitely implement something like this. Anyway, I really hope you devs get the problems in the path finding sorted out soon, it's being a real drag. I'm trying to play with the code myself, but all I managed to do is more or less narrow the problem down to the A* implementation in CCmpPathfinder_Vertex.cpp, which was a foregone conclusion.

Thanks, I feel welcome so far. Though, I must say I don't really know what you mean by "all are knew Problems"... ESL perhaps? Good guess, yes we were. I guess AI is broken? Then yeah, I agree, it probably should be made very plain and clear for those of us that are too short on patience or keen observation to find it in fine print or mile long threads. The bug is absolutely game breaking IMO. And clearly telling potential bug reportees what's known is a "help them help you" kind of thing. I don't like making a stink of bugs the devs already know, but I further dislike using my time trying to figure out if my exact bug is well known or not when the devs should know this info right off the top of their heads. This is what I find in the pathfinder.pdf concerning building placement... If placeable wall and raised terrain is treated as a special exception to overlapping, then... 1: So long as the wall segment sinks into the terrain, it looks 100% perfect. 2: You can only really overlap a small section of wall into the land, and wall doesn't spawn anything. As for being a known issue, I looked around a bit and I didn't see anything that suggests such either. Probably very low priority if it is known. Though IMO it's quite game breaking. What's the point of building walls if enemy units can get past gaps you can't remove? Now It could be said that one can always build a contiguous all encompassing wall. However, part of the strategy/fun of RTS game play is using the terrain to ones advantage. And walling off sections of the map is a great way to do this. Can't deal with it, there is no "no-formation" formation. Though I suppose I can just keep my siege out of the woods. I took a quick look at the problem with the dev-panel options, and I could be wrong, but it looks like if a unit comes up to two impassibles (trees) that are arranged such that there is a gap between them smaller than the unit clearance, but larger than a navcell, it will at first choose to travel as if there is enough room, then stop when the unit actually reaches the junction, do to an imminent collision. If I'm right, the best solution is probably to treat single gaps as obstructions and fill the navcell, then hope it won't lead to some kind of game-of-life like chain reactions. What do you mean extremely bad? A* is an great path finding algo, and A* + JPS is even better. Are you talking about the implementation? I think it is probably implemented as good as can be, but admittedly, I do think more/better optimizations could be had if devs and players were willing to accept the small inconvenience of sub-optimal path finding. I also think there is more room for pre-computing some of the path, many map obstructions are left unchanged for comparatively long times as far as a fast path finding algo is concerned. Finally, make it so the AI makes every effort to group units whenever possible, and that the system does rough paths for groups as a whole, rather than on a unit by unit basis (which is a given honestly). In the end, large chunks of CPU time could probably be saved doing any of this.

Hi. First, I am fully aware that some of these bugs are likely duplicates, comes with the bug report territory, so deal with it. (Think, would it be better if I not report anything at all?) Also, I am not criticizing the game devs for any of these issues, this game is complex, so obviously bugs are going to happen. And considering I see an alpha that is more like beta quality, respect for the team is definitely deserved... and given. Well done. Anyway, on to the issues I see. 1: Game slows down with large number of units, It does so in a jerky "stop-&-go" fashion. (known bug) 2: Game becomes desynchronized over time during multiplayer to the point that each player is seeing a completely different game than the other. All players (except host) leaving and then re-logging into the game fixes the issue momentarily. But players receive a "de-sync error on turn" message each time they join, and the game will again desynchronize after only a few seconds. I suspect that whatever is responsible host side for syncing the game during normal play can die randomly, an extra watch dog routine that checks or restarts the synchronizing code every so often would probably be a simple workaround for this. 3: Placing build able walls up against natural wall is quite broken. Not only do you have to try obnoxiously hard just to get it so there is a clean wall with no gap, but what you still end up with is a gap large enough to let units through 60% of the time. I suggest just melding a short wall chunk off of the joining sections of wall right into the cliff side when build-able wall is placed a certain proximity to the natural wall. The game would honestly look and function perfectly fine this way by most standards, and it should be easy to do. 4: Units will not move as a whole group until their formation animation is completed. This makes a group of units "lock up" in the heat of battle if you are clicking furiously, as they never complete the formation. I suspect the code probably does something like "on right-click { CreateFormation(); MoveUnits(); }". This should probably be changed such that the the create formation function either has a separate case/criterion for activation, or is outside the right click action altogether. Now, players really shouldn't be clicking more than one time to accomplish a single task, but it's also true that a good program will be made to safely handle "dumb user input". 5: If you move a group of units into forested terrain (~10 or so), they can get stuck when you're trying to move them out. I'm not sure exactly what causes this. I suspect that it has to do with the above bug, and a single unit is just getting stuck behind trees or something. A game play workaround is to issue commands to leave the forest one unit at a time. I would be tempted to call this a feature honestly. In real life, moving a large number of units through obstacles is part of the logistics of war. But the same effect could easily be had with an engine performance boost by making forest intangible and simply have an area of effect speed penalty. We do have mixed systems, but consider it generally... AMD_ATI_WinSeven_0 A.D. Alpha 13 Magadha