causative

It would be more useful to have "resource value destroyed" stats instead of "number of units/buildings destroyed." "Resource value destroyed" would multiply units/buildings destroyed by the cost of those units/buildings. That way, killing 50 women would not count the same as killing 50 champs. Starcraft II uses this system. (To get a little fancier - adjust resource weights according to how valuable that resource is, so that killing units that cost metal gains you relatively more score). Kill/death ratio could then be replaced by a more useful "combat efficiency" score - the ratio of the resources of the enemy that you destroyed, to the resources of your own that were destroyed by the enemy. This would help you figure out whether a certain strategy is cost effective or not. Total score should then be: the total resources you spent plus the value of enemy units or buildings you destroyed plus twice the value of units or buildings captured from the enemy (capturing counts twice because it both takes from the enemy and gives to yourself) minus the value of your own units/buildings that you deleted. (If you resign, that counts as if you deleted everything you had remaining) To see the logic of this, consider a team game such as 4v4. The "strength" of either team at any point in the game can be approximated by the total value of all the units and buildings owned by that team, which will go up and down over the course of the game. The four proposed factors for total score count your total contributions to the difference of (your team strength) - (enemy team strength) over the course of the game. Those 4 factors for total score have the nice property that the winning team is guaranteed to have a greater total score than the losing team - indeed, even if the game ends prematurely, the team with a higher score ended with a higher total value of units and buildings. Also - in all 4 factors, sheep should not be counted. (If you did want to count them, producing a sheep would fall into factor #1, and butchering it would fall into factor #4, canceling itself out).

Since currently there aren't very many players in the multiplayer lobby, this means that I frequently come to the lobby and see that nobody's there, and that I can't start a game. So I leave. That exacerbates the problem of there being few players! I'd like to log on only at peak times of day, or peak times of the week, so there will be plenty of other players. But I don't know when those times are. If many people knew what the peak times were and logged on at those times, we'd have lots of players at those times and everyone could find games easily at those times. And at other times, everyone would know not to bother, and just to wait for a peak. What are the peak times of day or of the week? It would be nice if that information existed somewhere public and obvious.

I think flashing dots for attacked units should be replaced with something else. It doesn't stand out enough for such an important event, especially with the default flash rate which is very slow. It takes me a few seconds looking at the minimap to figure out where the flashing units are if I'm being attacked. It would be better to have flashing dots for enemy units (more rapid flash rate by default, like 0.5 sec), and if you're actually attacked, perhaps draw a big red circle on the minimap over the attack location so you can't miss it. That's what Starcraft does.

Just a thought - in addition to more visible resource colors, it would be nice if the minimap showed enemy units much more obviously. For instance, enemy units in visible range should be rapidly flashing. New enemies coming into sight should have a chat message "Hostile <civ name> sighted!" (e.g. "Hostile Gauls sighted!") It's too easy to get killed and not know it because you were looking somewhere else.

Rather than simply making spies or thieves invisible - wouldn't it be much cooler if the spies could disguise themselves as enemy civilian-soldiers? Maybe something like http://wiki.teamliquid.net/starcraft2/Changeling_(Legacy_of_the_Void) . It could work like this: the player produces the spy and sends him towards the enemy. When the spy sees an enemy civ-soldier, it automatically changes allegiance to the enemy and takes on the appearance of the enemy soldier, so it is actually an enemy unit now, able to blend in by e.g. gathering resources. The spy remembers its former allegiance however, so the player who produced the spy can also give it orders and see what it sees. As soon as the spy changes allegiance, its stamina starts to decrease, and when the stamina reaches 0 (after several minutes) the spy changes back to a spy and will be targeted by enemy units. The enemy player could also select the spy and delete it, if he notices. If the spy escapes, he has to wait until his stamina reaches full before he can go undercover again. Thieves could work the same way except that they have a tiny vision range while converted to the enemy (spies should have a large vision range), and when thieves return resources to an enemy dropsite, they actually decrease the amount of that resource for the enemy. Before a thief's stamina runs out, he should be able to steal several times his cost in resources if the enemy player doesn't notice. There could also be "assassins" which work like spies, except that after having been undercover for a while (stamina below a threshold), the player who produced the assassin can order it to attack an enemy unit with a melee attack. If the melee attack connects, the enemy unit instantly dies and the spy is unmasked (stamina set to 0). Assassins should be pretty expensive, like 200 metal 200 food, to counterbalance the fact that they can kill heroes.

Well, here is the rough code I have so far. It achieves what I wanted it to do - large armies can stick together fairly easily without formations as long as they are in an open area, and it does reduce short range pathfinder use in those situations. However, there is still a problem, which is that units can get stuck against static obstructions. I think that may have something to do with the short range pathfinder being too optimistic about being able to walk around static obstacles when the navcells block the way (and the units have been bumped off the long range path by sliding). I'll still be tweaking it to see if I can solve that problem. Meanwhile please give it a try! For the most part this is 2 changes. First, units slide against each other parallel to the path, as I mentioned above. Second, units move in an order determined by their long-range path length - units with shorter paths move first to make room for those behind them, who usually have longer paths. A note - one interesting thing Starcraft II pathfinding does, is allow moving units to push stationary allied units out of the way. It might give a nice aesthetic to try that as well. Another note - this patch is far from polished. "It compiles" is about what can be said for it! Please don't murder me over the coding style, which I'll clean up a bit before submitting on trac if I can fix the units-get-stuck problem. sliding.diff

Finding units (targets?) within a limited area is optimized with SpatialSubdivision and should be much faster than O(n) per unit, closer to O(log n). If it's not then that could be fixable. SpatialSubdivision is defined in source/simulation2/helpers/Spatial.h. I know that at least the pathfinder/unit motion uses it when checking for collisions, hopefully it's used elsewhere as well.

Then what takes O(n^2) in the number of entities? Could it be done more efficiently?

What algorithm do you use that takes O(n^2) in the number of tiles?

Still working on this. So far I have implemented the following changes: When a unit tries to move and is obstructed by another unit, instead of stopping and asking for a short-range path, it will just walk all the way up to the second unit. From there it will attempt to "slide" along the side of the other unit's obstruction square. This "sliding" allows units to walk around each other without having to invoke the short-range pathfinder, which means they don't have to stop and can keep walking. Units only ask for short-term paths if the "sliding" is failing to make progress (unit is stuck and cannot slide). When a unit is following a long-range path, it only attempts to move parallel to the path instead of passing through every waypoint. This reduces the tendency for groups of units to travel single-file over long distances. Units will still follow short-range paths exactly, and will travel to the destination exactly. The combination of these two changes allows groups of units to get moving faster, and as they move they group together much better instead of narrowing to a single-file line. It also improves performance, because the "sliding" dramatically reduces the number of calls to the short-range pathfinder. I tested performance in the "combat demo (huge)" scenario. There are also some bugs where units get stuck - I've been working on figuring out how this happens and preventing it. It happens rarely. There's another issue. The groups of units are still not sticking together closely enough for my liking. They still bump into each other and don't all start moving instantly. To make units move together as closely as Starcraft marines, it will be necessary to have the units in front of the group move first, to open a space so that the ones behind them can walk forward without bumping into them. My plan for that is to let units wait for up to one other unit before they start moving. Here's a scenario illustrating how it would work. Unit A wants to move If A can freely move, it does so, and is finished for this turn. If A is obstructed by a unit B, and B is moving but has not yet moved this turn, then B remembers "A waits for B." Then A is done for now, but will try again later. Now unit B wants to move If B can freely move, it does so. Then B remembers "A waits for B" and tells A to try moving again. Unit A tries to move again (on the same turn, because B told it to try again). If A can freely move, it does so. If A still can't freely move because a unit C obstructs it, then A just moves as far as it can. It will not wait for C; it may wait for only one other unit per turn. However, I don't know if this kind of detailed ordering is possible with the component message passing framework. There is an alternative, which would be to sort units by their distance from the goal, and have units that are closer to their goal move first. However, that has its own problems and might be slower because it's O(n log n) instead of O(n).

Right, plus an instance of fixed is the same size as an i32, so there wouldn't be any performance benefit.

The actual data for a fixed object is an i32, right? So why not have "typedef i32 fixed" and instead of using a CFixed class, just have utility functions for operating on i32 as fixed-precision numbers.

I want to talk about some problems with pathfinding for large armies and proposed solutions. I would implement these solutions and submit a patch. If you have a big group of units gathered together with no formation, and select them and click for them to move somewhere across the map (or even relatively nearby), two things happen. The units in front start moving immediately, but it takes a long time before the entire group is moving. The group narrows into a single-file column as each unit tries to follow exactly along the planned long-range path. Neither of these things is what the player wants. The army would get to the destination faster if every unit started moving immediately, and it would be more effective once the fighting starts if it stayed together as a clump. The more spread out the army is, the more vulnerable it is. I want to pause here and say that I don't intend to do anything with formations. These changes can be accomplished through individual unit pathfinding alone. I want to compare this to other RTS games such as Starcraft II. In Starcraft II, if you have a clump of units and tell them to move, the entire clump instantly start moving, and stays together as a clump. You can see examples of Starcraft II pathfinding here: https://www.youtube.com/watch?v=x0gSVKVZ4YU. Throughout the video, notice how units stay in tight groups, even as they move around and change direction a lot. If they split up, that's generally because the player manually split them up by telling part of the group to go one way and another part to go another way. Starcraft II has no formations. So how can 0ad work like this? I plan on the following changes. For reference, this is the current pathfinder doc: http://trac.wildfiregames.com/browser/ps/trunk/docs/pathfinder.pdf Add additional information to units giving their expected direction. This is a vector saying where and how fast the unit is probably going to move in the next turn. It doesn't have to be perfect. If you give a unit a walk order, its expected direction would be immediately set to be parallel to the long-range path to the destination. Otherwise, a unit's expected direction would be set to the direction it moved in the previous turn. This information would only be updated once per turn. For the purpose of short-range pathfinding, units ignore units whose expected direction would move away from them fast enough that there is no expected collision during the next turn. This should solve the issue where it takes a long time for a group to get moving because of units treating units in front of them as obstructions. As a side benefit, this would improve performance because the short-range pathfinder would have fewer edges to consider!! After short-range paths have been selected for units, units with short-range paths that are nearly parallel to allied units adjacent to them, should have their paths adjusted to be exactly parallel. This would prevent units from converging into a single-file column over long distances, by keeping a group moving in a parallel direction. A unit is considered to have passed a waypoint (but not a final destination) if the closest point on the long-range path is at or beyond the waypoint. This is necessary in combination with change 3, to keep units from insisting on stepping directly on every waypoint even when other allies who were going in the same direction are in the way. edit: After further examination, I see there's another major reason for why groups of units take a long time to fully start moving. Units ask for a new short term path as soon as they encounter an obstacle, even if the obstacle is moving. Asking for a short term path causes the unit to stop for a bit. You can see this by ordering a cluster of stationary units to move with the speed set to Turtle (0.1x). You can see units freeze in place for a second, waiting for a path, before starting to move in a direction perpendicular to where they were ordered. To fix this, units should keep trying to move for a short period of time if they were obstructed by a moving unit, and only ask for a new path if this doesn't work. This would be in addition to the other changes. As it would result in fewer calls to the pathfinder, this would also improve performance. staticsliding.diff

4

A clearance of 0.8 for large units - same as for default units - looks OK and solves the pathfinding issues. I mean, 0.8 works for babylonian scythed chariots which appear larger than most siege engines or elephants. A value of 2 is a middle ground and also looks OK.

Siege engines are kind of a pain to use, and most of that is their poor pathing, which is a result of their large bounding box. They have trouble fitting through areas that normal units can fit fine, and as a result will often randomly turn around and go the opposite direction from what you want. Imagine siege engines appear the same size they do now, but have a small bounding box, similar to chariots or other cavalry. That way you could just send them in with the rest of your units and they would find targets by themselves. The case against doing this is that it would look somewhat less realistic - but we don't consider that a problem for chariots or cavalry, so I think we'd just get used to it.

It sure would be nice if multiple units could be queued up at a production facility without having to pay the unit cost until the unit actually starts being produced. Other RTS games such as Starcraft allow this. It would eliminate a lot of unnecessary clicks, especially when it comes to sheep. This would free players to pay more attention to controlling units in battle, which is more interesting anyway.

Aztecs and Incas weren't around until hundreds of years after 1000 A. D. Mayans were around in 0 A. D., but they wouldn't have encountered any of the other civilizations in the game 0 A. D., so I don't think it would work thematically. Plus, the Mayans that were around in 0 A. D. only had stone age technology so they would have been no match for European troops of the time.

The problem with using siege and citizen-soldiers to destroy buildings is that siege is easily destroyed by melee if it's not surrounded by soldiers, but citizen-soldiers are unable to withstand defensive arrows. Suppose that defensive arrows were nerfed so that they are only as powerful as the ranged attacks of garrisoned units, with a small bonus. And eliminate "sentries" so that if you want your tower to shoot you actually need archers in it (not spearmen). Here's another idea: have siege weapons provide +20 pierce armor to infantry that are within like 10 meters of it. Units close to the siege weapon would be effectively "garrisoned" in it, protected against arrows, but still able to fight in melee to defend it. Welcome borg-! Just so everyone knows - borg- may be the single best player right now.

There's another way to do friendly-fire targeting efficiently. Simply designate the archer's current target to be the closest enemy unit to the archer (using a space-partitioning tree to find this unit). If there are allies along the line the arrow would travel, and those allies are not right next to the archer, the archer doesn't shoot, and (crucially) doesn't choose a different target either. This would be fast, and result in correct targeting in most situations. In particular it would result in correct targeting if you use archers the way they were historically used - when no allied units except the archers/skirmishers themselves are in the line of fire. If the user has told the archer to attack a specific unit then that unit would be the archer's current target, instead of the closest enemy unit.

Suppose you could do that efficiently. For example, instead of checking that the exact line of fire is clear for each archer, instead for each enemy unit check whether there are friendly units within a radius of 10 meters, and set a flag on the unit that exempts them from ranged targeting if there are. Then, have friendly fire only apply within 10 meters of the target. This way, you don't have to check each enemy unit for each archer; you check the enemy unit once, and that tells whether he can be targeted by any archer. Limited ammunition is similar to Mana in a game like Starcraft II. Starcraft II is far more micro-intensive in combat than 0AD and that's seen as a positive factor; it allows for more interesting and diverse battles, and a greater influence of player skill on the outcome. If ammo regenerates slowly over time there doesn't have to be much shuttling. Also, if the ranged units flee by themselves when out of ammo, that reduces what the player must do.

Historically, archers and skirmishers would harass the opposing army before the main fight, and switch to a melee weapon once the armies met. This was because of two reasons: first, friendly fire was a thing. You didn't want your archers shooting into a battle if they'd be hitting your own men. Second, they had limited ammunition. A peltast would only carry a small number of javelins, such as three, which they would throw before the battle proper began. In this game (and in many other strategy games) ranged units have a completely different role. Two groups of melee units (champions typically) will engage, and the ranged units stand behind their melee units and shoot towards the backs of their own allies as they are engaged in combat. Mysteriously, their shots always avoid the backs of their allies, and only hit the enemy. This makes zero sense and is not historically accurate. Here's a more realistic mechanic. Friendly fire exists. Ranged units (including fortifications) will pick a different target or refuse to shoot if it would hit their own allies. If they accidentally hit their allies, it does damage. There would be no friendly fire at very close ranges, so that you can have a few rows deep of ranged units that can shoot past each other at the enemy. Ranged units have limited ammunition. Peltasts have 3 javelins, archers have maybe 10 arrows, and slingers can have 50 stones. Cavalry can carry extra ammunition compared to infantry. When a ranged unit is out of ammunition, it will pull out a dagger and fight weakly in melee, or automatically flee. Ammunition regenerates very slowly over time, or rapidly if the unit is garrisoned. In compensation for these limitations, ranged units (except fortifications) do more damage.

Yeah, I think destroying your own building should be slower. The issue with capturing is that if the opponent is alert, they will delete the building just before the capture bar reaches 50%. So whether the capture actually succeeds only depends on whether the opponent is alert with good micro. You can't forcefully capture a building if the opponent doesn't want you to. Alternatively - instead of the building going down instantly, after you press to delete it, it simply starts taking damage over time as if a battering ram was working on it. This would be cancelled if the building's capture bar goes below 50%.

Healers apparently don't do anything unless you have them stand directly in range of injured units. If the healer is standing just out of range of an injured unit, it will not walk closer to heal it. If you ctrl+right click with the healer, it will simply walk past injured units, ignoring them. Suggestion: ctrl+right click for healers should make them stop and heal any injured allied units along the way to the destination. That way you can just select your entire army including the healers, and ctrl-click to attack towards a destination, and the healers will actually help in the fight. If a healer is idle nearby injured allied units, but out of healing range of them, it should walk forward and heal them, unless you have set the healer on hold position.

Even walls, gates, and towers generally were not fully destroyed during combat. Even a battering ram would just breach the gate or open a hole in the wall, not destroy the entire wall. And even once you've captured a stone fortification how are you going to destroy it? It's not easy to disassemble a huge pile of stone. It takes a lot of workers a lot of time. Not something you'd do in the heat of battle. The main way buildings would be destroyed in combat would be to burn them, if they were wooden buildings. Aside from that they were occupied, not destroyed.