Chakakhan

Hmmm, any U/I work done for tributes/buying /selling yet? That seems like it would be a reasonable chunk of work. Good bang for the buck I think.

I really like the spy idea. Adds some interesting potential strategy. Might be neat that if/when he gets captured they beat information out of him and you get to take a look at his base for 10 seconds or something.

Hi Ian, nice to virtually meet ya! Hope to see you around a lot in the future. Cheers!

Please see if you are still getting this error with the latest build. Cheers!

Hi Yves, good job on the scripts! The game was failing at run-time due to the the DELAYLOAD linker directive - it didn't like it. It caused OpenGL to fail on three different machines and on win7 and xp all with current drivers. I commented this out and it works now. I also commented out the extra_checks flag as it was throwing exceptions about casting down to smaller types all over the place. I attached a zip file in the same format as your previous one, so it can be installed in the same way, just copy it right over the existing files. There is no testgen project in the solution right now, but I see the code for it in the premake script. I will take a look at why it is not creating the project for it. premake4-v2.zip

There are issues with the Premake4 scripts. The solutions will build, but they throw exceptions when they try to initialize OpenGL. I have tested this with VS2010 Express on XP, VS2010 Professional on Windows 7 and VS2010 Ultimate on XP. All have the same problem. Side note: on my Windows 7 box, the exception dialogs are not showing up and the application hangs waiting for input into the invisible dialog box (I have multiple monitors on that machine as well, so that may be a contributing factor to the dialogs not showing up). I also tested the Premake4 2008 scripts by upgrading them into the same 3 environments above and got the same error. I checked all the compile and link switches and it all looks the same. I am going to take a look at the Lua scripts and see if I can figure anything out.

Makes sense, I think the tiles are currently too large for this to work out visually (check out my second picture above). One of the things we are trying is to decrease the tile size and see how that works out. I am making a change that will make the tiles 2 meter squares instead of the current 4 meter squares (so 4 tiles can fit in the space occupied by one now). That should make that work out a lot better visually.

Jason, I think that picture is a great example of how it should work. If you pack trees tightly there is no passage period. But what about this (from Jason's other link above): Forest Units – only units with the Boolean attribute of walking in forests may walk in Forest type. Structures – no structures may be built. A special note about the forest type. When a tree is placed on the terrain, the tile that the tree is placed on has the terrain's secondary texture skin changed to a forest type. When a cluster of trees are placed in adjacent tiles it changes the terrain enough to make a 'closed' forest terrain which means that all eight tiles around it also have a tree on them. When that is the case, the terrain is now of the forest type and there are special permissions applied to it. How dense do the trees need to be for an area to be considered a forest?

Good question! If the long path finder can't find a path then we try with the short path finder. If the short path finder finds a path then we are good, if not we have problems. There was a bug in the code which was causing units to get stuck. If a unit was in formation and the long path finder failed then the short path finder didn't always run. That is fixed, but we are still looking at ways to improve pathing so that the default pathing code handles most issues and we avoid having to code too many special case solutions. It is a lot less likely that you will get stuck with the latest updates, but there are a few conditions where bad pathing can happen because of the issues discussed above. I am currently working on a task to test a couple of solutions and see which one gives us better pathing. Cheers!

The changes will actually make it easier to navigate in the forest. Ras, that could be achieved by making forested terrain very undesirable to the long pathfinder. This will be possible.

Well, not sure what the story on that is. I think there should be forest that are so dense that it makes a lot more sense to go around, especially an army with supplies and all that stuff. You would certainly have to make pathing exceptions if you wanted to make a dense forest passable, the obstacle code would have to handle trees in a special way - at a certain density, the trees are pathed differently. Otherwise you could pass through trees everywhere and thats not good. So one of the game designers will have to let us know what the desired goals are and then we can tell them how reasonable that is from a code perspective. As you say, forest make the problem more likely to occur and it is also very obvious when it happens there. The same things are happening in large battles, but its just not noticed as much because units are getting killed etc. Other things like lag and jerkiness become a much more obvious problem than bad pathing in that situation. Solutions to performance problems are also being designed and mulled over as well. As Philip mentioned, the code is not using highly optimized versions of the algorithms yet. It's just better to get game play elements right before optimizing it too much. He has lots of ideas on how we can optimize the code once it is in a reasonable game play state. I totally agree with this!

Sounds good, I will start on this tonight.

Well changing the resolution of the pathfinder grid might be the cleanest solution. I probably should try both ways and see where I run into trouble with each one. Then we could also get an idea about the performance impact of each solution as well. So with the rasterise change are you proposing that we process all unit type objects the same way or that we separate out tree/small objects and process them differently like I mentioned?

That sounds reasonable. I will take a look at some profile dumps.

Well, yea, trees are a little different aren't they. Seems like we need a different algorithm for them, maybe one that handles small objects better. I don't think one tree should be able to obstruct an entire tile by itself. And if two trees are on the tile, but on the same side then they probably shouldn't block it either. But if there are two trees each on opposite sides of the tile then they probably should. What if for trees (and other small objects) we broke the tile up into thirds or some other reasonable size and write the algorithm so that it is based on a small object intersecting more than one of the fractionalized tile areas? For example, if we broke the tile into thirds and we got a hit on the tile for two of the three we would mark it blocked for pathing. We would need a new way to specify this type of object so that we can differentiate it from the other unit types (we may already have some way to do this - maybe the non-moving flag or something?). Assuming we broke each tile into thirds, we loop through them for each unit and if we get a hit on a tile section, we see if another section of the tile is already hit and if so mark it blocked. That way we still only have to hit each tile once per tree. Thoughts? We should probably refactor those names at some point as that is a little confusing.

As I'm testing the pathing stuff over and over and over and over I have noticed that it takes 10-15 seconds for the performance to settle down after a game starts. This is to be expected with the JIT since it compiles things as they get invoked. I was wondering if we could get the JIT to compile things while we are on the game setup screen while we are sitting idle waiting on user input? We could invoke the JS code with some data that would get the JIT to compile most of the code. I am probably doing a bad or worst case scenario as I select a group of units and start trying to move them around immediately. This causes a lot of JS activity (formations and stuff) in addition to all the AI startup stuff thats going on at the same time (UnitAI and Computer AI startup). This isn't a high priority, but it does make the game really sluggish at the start so it's something we should think about.

I made this change when researching and they don't get stuck. I think we should change this so that trees are treated similar to other static objects and see how it feels. If we make both of these changes I think we will be a lot less likely to have this type of issue. I will code this up and put up a patch for your review when I get home from work tonight (unless you have already done it )

I found a great quote from David Pottinger, the guy who was the technical lead on AoE2. It backs up my statements about cost and complexity: It is interesting to note that Pottinger writes, "Pathfinding is one of the slowest things most RTS games do (e.g. Age of Empires 2 spends roughly 60 to 70% of simulation time doing pathfinding)." Having played AOE and AoE2, and being aware of the fairly small size of the maps (usually less than 100 x 100 tiles) I would have thought it would have been possible to pre-calculate paths and store them leaving the CPU time for other things. He follows that up with a list of things to consider, the following is the first item on his list: Terrain analysis doesn't need to be exact. If you try to make it perfect, you'll either end up spending a lot of time tweaking heuristics or you'll have a lot of extra areas that really don't buy you anything. The article summary is here: http://www.gilgamesh...es/page_29.html I have a copy of it if you are interested let me know. In this article he talks briefly about terrain analysis for pathing and AI.

I left out a lot of the edge case details in my description, size and clearance are actually part of the pathing consideration. The short and long path finder need to agree on what is passable and what is not. They currently don't always agree completely. Performance is dramatically affected if you decrease the tile size (therefore increaseing the total number of tiles), so you can't just reduce the tile size to get higher resolution without taking a major performance hit. That is pretty close to what we have, what you are calling medium and short are both rolled into the short pathfinder. Yep, that is certainly possible. It could be considered bad map design to create a map like that knowing that large groups of units roaming around is a part of this type of game. On the other hand it could be considered a strategic challenge as well. Either way I think it should be visually evident to the player what is going on. Obviously we need to make some code adjustments. I just don't think we want to make a knee jerk change until we as a team have looked at this issue holistically and come to a consensus about what constitutes good game play. Because that is really what this is all about! We are currently using the A* algorithm with lots of optimization for the long path finder and it is considered the best for this type of problem. There are lots of adjustments that can be made and lots of fine tuning. Its just a tough problem and it is very easy to fix one thing while breaking a dozen others if you aren't very careful. The current code is very well written and well designed so once we figure out the right solution, I don't think the changes will be that difficult.

There is currently an issue with the pathing that allows units to get stuck in a forest. To make a long story short, it has to do with the long path finder and the short path finder having different ideas about what is a passable area and what is not. I did some play testing today on other systems and the behavior is pretty much the same for all the 3D RTS games I tried (AoE3, AoM, AoEo). So in the picture above, from AoE3, the green arrows show where units can pass through and the red X's show where units cannot pass. The map designers were careful to make it visually clear where you could and couldn't pass and the system tolerances were designed along those same lines. Pathfinding In 0 A.D. Let me explain a few technical things about the way we "pathfind" and move units around the game world. 0 A.D. uses a "long path finder" to find the best path from the starting point to the requested destination (if one exists). It basically breaks up the terrain into a series of square "tiles" and then uses an algorithm (A* basically) to figure out a path to our destination at the tile level. It figures out if a tile is passable or not and if not it will rule out any path across that tile. It eventually finds a set of adjacent tiles that will take us from source to destination, or it fails and no path is returned. It then creates a set of waypoints along those tiles and saves that as a units long path. The long path doesn't worry about moving units, it only considers static objects. It is not useful to consider moving units at this level because it could take minutes to get to a destination and by then all the non-static units might have moved. Then 0 A.D.'s short path finder finds a path to the first long path waypoint using a different algorithm. The short path algorithm doesn't navigate at the tile level like the long path finder, it navigates the best path based on looking at the objects in its way. It can consider other moving units and does so if it runs into an obstruction along its path (actually the unit just requests a new short path telling the algorithm to consider moving units). When it reaches the long path waypoint it was headed for it recalculates a new short path to the next waypoint along the long path. Once a unit reaches a long path waypoint it requests a new short path to the next long path waypoint and so on until eventually it reaches its final destination or it is blocked. This is a simplification of the process as the algorithms have to account for changes to the game world. For example, what if a wall was built between the time a unit requested a long path and the time it reached the location of the wall. The wall now invalidates the units long path, so it has to recalculate a new long path. There are lots of other corner cases that must be considered as well (feel free to look at the code for the finer details ). Now with that explanation, hopefully the image below will make some sense. This is part of a screenshot taken from 0 A.D. It is a forested area near the center of the map "Median Oasis". It is currently very easy to get units in a formation stuck in this area. I took this screenshot with the 0 A.D. developer option "pathfinder overlay" turned on (press shift+D to get the developer menu). This places a red box on all the tiles that the long path finder considers impassable. Take a look at the image below: First off notice that it is not very clear from a players perspective which paths are passable and which are not. Look at the wide spot between the two trees just in front of the cavalry unit. As indicated by the red tiles, the long path finder does not consider that area passable. Secondly notice that the area where the horse is located is completely surrounded by red impassable tiles. Remember we calculate our path at the tile level in the long path finder, but the short path finder uses a different method. The short path finder uses the blue squares around the trees and the unit to see if there is enough room for a unit to pass through. In other words, if the square around the unit can be moved between the squares around two trees, the unit can pass between the two trees. So when using the short path finder we can easily pass through that wide opening directly in front of the cavalry unit. Under most circumstances a combination of long and short path finders gets the unit through that area without any problems. As far as I know a single unit will not get stuck going through the forest with the current version of the code in SVN (I tried to reproduce this for over an hour and could not). Formations Things get a bit more complicated when a unit is traveling in formation. When a unit is in formation it is following a proxy unit which actually holds the long path for the entire formation. So when you tell a formation to move it actually generates a long path for a placeholder or proxy object which represents the formation. All the units in the formation actually follow a particular point on this proxy object which represents the units target position in the formation. As the proxy object moves along the path to the destination the individual members of the formation will calculate their long and short paths to their target position on the proxy object many times along the way. The differences between what the long and short path finder consider passable is what causes units to get stuck. If a unit in a formation is in the open area where the cavalry unit is in the image above and both his long and short path need to be recalculated and the proxy object is already on the other side of the forest then we get stuck. The pathfinder tries to find a long path to the formation proxy and since he is in an area surrounded by impassable squares he can not calculate a new path and he is stuck. That is the bug in the current code and we are looking at the best way to solve that problem in code. It is also very important that we make it clear to both the player and the map designer what a passable area is. We need to decide on a clearance threshold and then we can adjust the code to match. Note that making this value really small slows down the algorithms. It should be something reasonable like in that first image from AoE3 I think. Any feedback or ideas are welcome. Cheers! Note: I am brand new looking at this code, so Philip or anyone else please feel free to correct any bad technical assumptions I have made.

Hi Gudo, Great tip! This is definately a great tool for experimenting with the AI scripts. Thanks for sharing. Cheers!

Hi Jan, I thought I had keep tabs selected in VS2010, I will verify that before I make any more changes. Cheers Hi Jan, I verified that I have the use tabs turned on. I usually use spaces, so its possible I'm used to typing in spaces and that is where they originated . Anyway, I will be more careful about that now.

Hi, welcome! Glad you are here. I am a new guy too. Folks are very nice around here and will answer questions and help you out. Cheers

Ok Jan, thanks for the feedback. Sounds like we are in sync. I noticed you found a window handle that worked with the clipboard, glad to see that! Also, I noticed how you cleaned up the error handling in wclipboard. A lot of the older code is coded similar to the way wclipboard was (little or no error checking returning nums or zero instead of symbolic constants), so I will follow your lead and make similar changes when I run into that type of code. Cheers

Yep, it would be nice to do some benchmarking with higher poly counts to see what the effect is.