Ykkrosh

(Bit distracted by other work and PhD-related things and thinking about formations etc, so I'm still trying (not quite succeeding) to get a more consistent rhythm...) Day 9 Did some research into pathfinding. Independent of the ongoing discussions about formations etc, it seems we could benefit significantly from a faster long-range pathfinder. In particular, the pathfinder needs to quickly plan an efficient route from one side of the map to the other, avoiding impassable terrain (cliffs, rivers, etc) and buildings. It doesn't need to be a perfectly smooth path, and it doesn't need to avoid other units - that's the responsibility of a lower-level module that computes the frame-by-frame movement of each individual unit as it follows the high-level planned path. (I said a while ago that I was only planning to look at the short-range pathfinder, but performance data suggests the long-range one matters, and changes to the long-range one might change the requirements for the short-range one, so I'm focusing on that for a while.) The current pathfinder is a pretty basic implementation of the A* algorithm, with the terrain and buildings stored as a 2D grid of passable/impassable tiles. It's reasonably fast - after a few minor simplifications and optimisations compared to the code the game currently uses, it can process about 4 million tiles per second on a fast CPU. But a standard map in the game might have 40,000 tiles or more, and in the worst case (when there's a very long and complex path) the pathfinder might have to process every one of those tiles, taking about 10msec. If you send multiple groups of units to attack the enemy at the same time, that adds up to a reasonably significant amount of CPU usage. That's still not terrible, but a secondary problem is that tiles are quite large. Our typical units are less than half a tile wide, but if two buildings are separated by as much as two tiles then it's possible for there to be no fully-passable tile between them, so the unit won't be able to find a path between them. If we could replace every tile with, say, a 4x4 grid of sub-tiles, then we'll be able to represent gaps that are a quarter of a tile wide, allowing much more accurate movement of units through complex environments. But then the pathfinder will be about 16 times slower, so we'd need to balance it by optimising the pathfinder much more heavily. There's quite a bit of existing work on pathfinding over tiles, from both practical and academic perspectives. Navigation meshes are common in non-tile-based games, but they're a bit tricky to update dynamically (e.g. when a building is constructed, or a tree is cut down), and the use of tiles allows us to use more specialised algorithms. Navmeshes might not always find the optimal shortest path between two points; they're just designed to find paths that are 'good enough' in most cases. MM-Abstraction (PDF) (designed for the game Dragon Age) is basically tile-based (non-convex) navmeshes. HPA* (PDF) is a bit like MM-Abstraction with higher-quality (closer to optimal) paths, at the expense of performance; you can adjust the tradeoff by tweaking the algorithm. (In particular you can choose the number and location of nodes on entrances into each region, whereas MM-Abstraction assumes a single node somewhere near the middle of each region). Jump Point Search guarantees optimal paths by simply computing the standard A* algorithm in a more efficient way (skipping redundant work). One concern is that most of this published work is based on maze-style maps, with a series of rooms connected by corridors. In an RTS game we generally have the opposite: most of the world is open space, with trees and buildings dotted around it, and a few very large obstructions (rivers, mountains, walls, etc), and no rooms or corridors. Some algorithms are explicitly designed to identify rooms, so they'll be useless here, and for others we need to be careful that they have the desired performance characteristics. Another concern is that some algorithms assume movement cost is uniform across the entire map. There are some interesting features you can get with non-uniform costs. E.g. you can make roads very cheap to travel along, which means units will prefer routes that use roads instead of slightly shorter routes that don't use the road. Or you could identify 'dangerous' tiles (within range of enemy defensive buildings) and make them more expensive to travel along, so the pathfinder will prefer paths that avoid dangerous tiles even if they have to travel slightly further. The game's current pathfinder supports non-uniform costs, but I'm now thinking that it's not really all that useful a feature, and it may add significant complexity, so it's probably best to abandon it and focus on getting basic uniform-cost movement working well. What I'm currently planning to do is experiment with JPS and see if it actually works in practice - it's nice to have optimal paths (to reduce the chances of players noticing weird behaviour), and it claims to be competitive with HPA*, but I think that will depend significantly on implementation details, so it would be valuable to have an implementation to test and optimise.

The best way to find out what dependencies are needed is to try building and see what errors appear about missing libraries . If you need quick feedback on error messages, #0ad-dev QuakeNet IRC is probably the best place to ask. I'm not aware of anybody trying to build on BSD recently so I don't think we can suggest anything specific - just need to try it and see what breaks.

I vote in favour of anything with non-ASCII characters ("ā" and "š" etc), because they're more fun

Thanks for the description . I filed a ticket and will try to look into it soonish (unless someone else wants to take over the font code ). I don't know whether the font we're using supports that properly, so that'll be worth verifying. If it's ugly then I think it should be easy enough to edit the OpenType font to fix the glyph placement.

We need people who can do everything . That's partly because we have lots of little problems in lots of different areas, so it's most valuable to have people who can fix problems regardless of what area they're in; and partly because the big problems usually involve the interaction of multiple areas, so we need people who understand all those areas and can work out how to tie them together properly. It's probably best to start by learning whatever you find most interesting yourself, and then continue expanding into new areas whenever you have the opportunity

I think my current uncertainty is caused by there being lots of different gameplay restrictions that will make things technically feasible, but not knowing what restrictions or combinations of restrictions would be acceptable from the gameplay perspective. E.g.: * Don't support formations at all. (By "formations" here I mean anything that involves a group of units acting as a coherent whole.) * Let each unit split off and act independently whenever it wants to, instead of forcing them to stay in a formation/battalion/etc with other units. * Restrict maximum formation size to maybe 6x5 units. (Any larger selections would consist of multiple formations that move independently.) * Make the environment very simple; allow units to pass through trees, don't have any narrow chokepoints, enforce large gaps between buildings, etc. * Allow units to pass freely through all friendly units and/or enemy units. * Don't try too hard to make units go exactly where the player clicked. Most open source RTS games don't seem to support formations at all - every unit moves individually to the target. AoM (and other Age games) lets units act independently (the formations are temporary and easily break up), and the maximum formation size is 6x5 (because you can only select 30 units), and units get blocked by everything (except other units in their own formation). Praetorians is apparently limited to 6x5 and units can walk through pretty much anything (including trees). BFME2 has similarly limited size and units can walk through friendly/enemy units. Rome Total War has very large formations which can walk straight through friendly units, and try to walk straight through enemy units (but get stopped when they hit them), and formations ignore trees (though individual units walk around them); the only semi-interesting pathfinding is inside cities, which have large gaps the formations can easily fit down. I suppose the fundamental question (which I'm still totally unsure about) is: what are our goals for the gameplay? There's some basic things like "don't be irritating for most players" (which a lot of commercial games have failed at), but what else should we aim for? There's a thousand designs that would be technically feasible to implement decently (including the designs from any existing game we can test and clone, and a small proportion of novel designs), so I think we need a structured way to evaluate which would be a good fit for our game. Otherwise I think the danger is of just saying "I like X", "I can't implement X, what about Y", "I don't like Y, what about Z", ... and ending up with a dozen random ideas but never reaching a good solution. The baseline for the current design is the Age games - what problems do they have that we'd like to improve on? Do we want formations to provide an extra layer of tactics to combat, because Age-style combat (throwing masses of units into a giant melee soup, as far as I'm aware) is too simplistic; or is Age-style combat fine, and we should avoid making it more complex? Do we want more or less micromanagement in combat? Do we want battles to be slower and more turtley, with a strong defensive formation able to block enemies at a chokepoint, or faster with enemies able to easily circumvent any defenders? Does supporting large numbers of units and/or large formations of units make the game better in some way, vs smaller (more easily controllable) armies? Do we want fancy formations so we're more historically accurate, or so we look cool, even if they don't improve gameplay? I assume people will have differing opinions about all these concerns, but I think it would be valuable to sort out those differences now and come up with a coherent set of design priorities. Then it'll be possible to come up with specific design ideas and evaluate them more objectively from both technical and gameplay perspectives, and end up with a solution that's as good as it can be.

In #960 the issue was that there's lots of different ways to write a character, and the font supports one way but the XML file used a different way, so I just changed the XML. "ī́" is harder because there's no Unicode codepoint for i-macron-acute. We can't support combining characters in the current bitmap font renderer even if the font supports it (since they rely on fancy OpenType features which we can't interpret at run-time); maybe it would be best to make the renderer support multi-codepoint sequences, then we can store the combined "ī́" glyph in the bitmap and use it when necessary. It'd be good if someone could file a Trac ticket listing all the known font problems

Thanks for the pointer. It seems to just be doing bog-standard A* over tiles (via engine/pathfinder/astar.cpp), and unit movement is constrained to tiles, and there's no special handling of group movement (the behaviour seems quite messy when you tell a large group to move to a point), so I don't think it helps here

That sounds like it doesn't address the problem that started this thread, which is that it's too hard to have wide formations walking around the map. Groups need to be narrow flexible column formations (at least as narrow as the BFME hordes) so that pathfinding works sensibly, or else need to not depend on sensible pathfinding (e.g. by refusing to automatically route around complex obstructions while in large poorly-maneuverable formations), or some non-simultaneous mixture of those. I don't think automatically creating battalions from arbitrarily large selections of units could work, since it would either make a wide formation which would be unsuitable for moving around the map, or a narrow formation which would not be generally useful if it contains more than about 20 units.

How does this automatic battalion proposal (edit: Android_'s proposal in particular) differ from how the game currently works, where groups of units join together into a formation when you tell them to move?

I checked again and it looks like the basic goblins are 5x4 with some jitter so they don't line up neatly, and the basic dwarves are 5x3 in neat rows. (I'm using the demo with skirmish maps for this.) I suppose it's more appropriate for games that focus more on combat than on economy (like BFME appears to). Seems tricky to e.g. combine it with the citizen-soldier concept - you probably don't want an entire battalion chasing after a chicken, so the units need to be controllable individually to let players allocate them to appropriate roles. But I suppose it's mostly a matter of taste, so we just have to pick one option and then do it as well as possible Yeah, designing the user interface is probably harder than actually implementing the algorithms. I think a common criticism of formations in RTS games is that they take more effort than they're worth - if you're micromanaging formation movement on a battlefield, it distracts you from developing your economy, so you might lose to an opponent who doesn't bother with tactics but can throw twice as many units at you. So it needs to be intuitive and easy to learn (else most players won't bother), and efficient to use (so experienced players can multitask while using it), and needs to give enough gameplay benefit (combat bonuses etc) to be worthwhile (but not so much that it's overpowered). That's what I'm thinking, like BFME or Rome Total War etc - you can only select the formation as a whole, and can only attack an enemy formation as a whole. This seems important if we're effectively forcing the user to do pathfinding themselves. I imagine it could display the outline of the current formation, and the outline of where the formation will stop moving (either green where the cursor is pointing, or red where it would hit an obstruction and stop), either when clicking or just when moving the cursor around the screen, so you can see where it's safe to move. By the general principle of making it simple to learn and easy to use, I think leaders shouldn't exist (except perhaps as a purely graphical effect, like in RTW where an arbitrary surviving unit carries a flag which you can click to select the formation) - they would add more complexity and micromanagement, and would make formations usable in fewer cases, whereas we want people to use them more. Hopefully most design questions can be answered by those principles and by technical feasibility. I'm not sure it's ideal to try to write down a fully detailed design in advance: the only way to see what gameplay works in practice is by playtesting, so we need a working prototype (with a willingness to change it later) before settling on a design; and with a relatively complex technical problem like pathfinding it's necessary to base the design on what is possible to implement efficiently, and we can't really know that until having tried implementing it. So I think in this case we need more of an iterative process to find something that works from both a technical perspective and from a gameplay perspective. I think the common approach is to discuss ideas on the forum until there's rough consensus on the basic concept, and then someone implements it and makes lots of minor design decisions themselves (or asks on the forums or IRC etc for input on those decisions), and then people test it and suggest changes or extensions. Then it's either good enough, or a year later we decide it's too broken and can see a better way of doing it and rewrite it, like in the current situation with formations

I played a tiny bit with BFME2 for comparison. (Not tested it extensively so this may be wrong.) Units are naturally in groups (hordes?) with e.g. 20 members. You can't control individual members, only the whole group. When moving a group, it seems to do a usual A*-over-tile-grid style thing for a group leader (don't know if there's an actual leader unit or a virtual leader), and the members run around to stay roughly in the appropriate formation slot. Members never get split up: if the leader goes around the left of an obstacle, all the members will go to the left (even if going around the right would be straighter and shorter for them). Units can (and usually do) walk straight through each other, including through enemies. If you send a group through a one-tile-wide gap, the units all squash up (and stand on top of each other) to fit through. If you select multiple groups and tell them to move, they seem to all find independent paths. Groups often don't go where you tell them to go - their target position seems to avoid getting too close to other groups or to obstructions (e.g. you can't make the group stop in the middle of a narrow gap, they'll always try to find a wider space). I'm not quite sure how building placement works - it seems they're squares oriented at either 0 or 45 degrees (depending on building type), and usually (but not always) you can't put them close enough together to block units getting between them. The map design guide says you should avoid creating narrow gaps and mazes etc, because they confuse the pathfinder or cause poor performance. Apparently there's some pathfinder exploits like clumping (normally only the front ranks can reach a target, but you can trick it into getting all the group's units into range), and people complain about the pathfinding being generally rubbish (although people complain about that in pretty much every RTS game ever made). I think the problem with our currently implemented game design is that we let players make giant formations and then send them across the map and expect them to stay in that formation and move sensibly. That's never going to be possible (unless someone can provide a counterexample, e.g. a game that already does this nicely) - complex obstructions will always require a formation to break up because it just won't fit, and our maps have lots of complex obstructions (rocks, forests, valleys, bridges, etc). Currently they break up in messy inefficient ways, and we need to handle it in a more controlled way instead. I think the following would be realistically implementable option (though still a bit vague): * When doing normal movement of a group of units, they always adopt a narrow column formation. (No more than perhaps 3 tiles wide (4 infantry units, or fewer larger units), which avoids most of the nasty edge cases when pathfinding). Column formations move with snaking (each unit basically follows the footprints of the unit in front of it), so they can be arbitrarily long and can follow bendy paths with no problem. They can fit through 1-tile-wide gaps by squashing up a bit, so the pathfinder doesn't need to avoid those gaps (though it should prefer to stay a tile or two away from obstructions when it has the choice). * When the group reaches its target, it'll spread out into a wider rough box shape if there's enough space to do so. (This would be a bit like what quantumstate suggested, searching sideways to find how much space is available, though only when stationary (which makes it a simpler problem since it doesn't interact with the pathfinder).) * If the movement target is very close (like half a screen width) and reachable in pretty much a straight line (not blocked by a river etc), the units in the group might just run towards it individually instead of forming up into a column first. * You can put a group of units into a battle formation (line, wedge, etc), which can be as large and as wide as we want to allow, and which provide combat bonuses. You can only do that if there's enough empty space for the formation. Battle formations don't do any pathfinding: they just turn to face the right direction and then head directly towards wherever you click. (You can shift-click waypoints if you want). If there are large obstacles in the way (larger than a lone tree), the formation will stop. The formation will persist until it's explicitly disbanded by the player, and you can't command an individual unit while it's in a formation. It's the player's responsibility to only activate battle formations when they are on an open battlefield and are willing to do more micromanagement of unit movement. It's the map designer's responsibility to ensure there are open battlefields where formations will be useful. The important thing is that we can have either good pathfinding in complex environments, or large formations, but not both at once. Since we want both, there needs to be a switch between the good-pathfinding-but-very-simple-formation and complex-formation-but-no-pathfinding modes, then each mode can implemented and optimised and tweaked independently. If there's no better option, I think the first steps in implementing this would be to focus on the non-battle-formation mode - remove the current formation buttons, implement usable columns for moving groups (including some minor pathfinder changes), and implement some spreading out at the destination. Battle formations can then be designed in more detail later.

All it should need is "sed -i s/jubot/qbot/ *.xml" which doesn't sound too much of a pain

I experimented a little bit with flocking here a while ago. That doesn't use a static formation layout to determine each unit's target, though - they all target the same point, and the distance constraints make them prefer a square grid pattern around that target point. I think the main problem I had was that it feels too springy - the units are meant to be intelligent humans, so it might look weird if they're sliding around and bouncing backwards and forwards, and I couldn't see an obvious way to avoid that. Maybe it would be best to revisit this kind of approach, instead of doing everything with perfect geometrical shortest paths (like the current implementation and like the Age games). If the units target appropriate points in the formation layout, that should stop them springing outwards when reaching the destination and losing the central attractive force. Then maybe some tweaking of parameters, and/or some kind of smoothing filter on the positions of the units' graphical models, would make it look good enough? Maybe I'll try playing around with my JS prototype a bit more to see if it can work better. (Other prototypes are also welcome )

Thanks for looking into this! Have you tried the config settings mentioned here? (I forget which file they go into; I think it was something a bit like startup/user.cfg on AoM; I have no idea if AoEO still supports this.) That might give some more indication of the internal workings in tricky situations. Making formations narrower seems like the easiest way to make them behave better. In this test with qbot it looks like the formations are 20x3 units, and I think it'll be pretty much impossible to make such wide formations work well in complex environments (with lakes and trees and hills etc) - they're just too unwieldy. Assuming we want to include proper formations like in Rome Total War, rather than Age of *'s much smaller and less cohesive groups, I was thinking that maybe we should intentionally make them poorly maneuverable. That's the cost the player pays for formation combat bonuses: the formation can only march slowly over fairly clear ground, and will refuse to even attempt to walk through a forest or around a lake, but if you manage to get it into position then it's a very powerful force. In that case, normal movement of groups of units would be more Age-like - smaller and narrower shapes (I think they supported at most 8 files and maybe 5 ranks? and in most cases it would switch to column shapes with maybe 4 files? and with no user-selectable formation types) which are therefore more maneuverable and flexible and can cope with walking through busy environments. We'd probably still want some improvements to the current pathfinder so it avoids sending the group through confined spaces, but much less major changes than trying to make it cope sensibly with massive formations. Yeah, columns should definitely do that. That's close to what we do already - there's a single 'formation controller' which finds a path to the destination and walks along that path, and then every unit chases after that controller (plus an offset corresponding to their slot in the formation). (The formation controller is actually invisible and not a real unit, but it acts a lot like a real unit.) What if a player selects a group of units, half of which are standing just inside their city wall and half just outside, and tells them to move to the middle of the map? I think they'd expect all the selected units to obey the order, and the ones inside the wall should run around to the nearest gate and join up with the other units - it seems bad if half the units get stuck inside and will never come out because they're unwilling to look for long paths.

I looked. (Only tested in Firefox; won't work in all browsers.) (Red lines are expensive (unreachable destination) pathfind requests; cyan lines are cheap ones.) That makes the problem fairly clear - a formation is circumnavigating the oasis, and the units on the right half of the formation think they ought to be standing in the water in order to match the formation, so they are repeatedly trying (and failing) to pathfind their way into it. New question: How should this be solved?

Currently the game occasionally has terrible performance. I want to improve that, but first need to work out what situations are particularly problematic. I tried a 20 minute qbot-vs-qbot match on Oasis II (in replay mode with no graphics), and got the profiler output here. With some extensions to the newer profiler it's possible to drill down into the data, which looks like this in the slowest sections. That indicates most time is in the long-range pathfinder ("ComputePath"), and the "steps: 40001" indicates that it's failing to find a path to the destination so it tries searching every reachable tile in the map before hitting the arbitrary limit of 40000 and giving up. I need to look into why it's unreachable - it could be that the destination is in the middle of a building, or maybe it's an unreachable resource or something. Then need to work out how to make it better.

The main reason for initially implementing it that way was that it simplifies the GUI (the unit details panel just needs a single resource icon and counter). It'd be possible to keep the GUI simply and have units drop little piles of food/wood/etc when picking up a different new resource, instead of magically losing their load, but that seems like more effort than it's worth.

I think the most relevant images are here, in particular background.dds for the main background. (Download then open in something that supports DDS textures (I think Gimp does by default).)

Thanks, so it's not just historic_bruno . I committed a thing that hopefully fixes this error with the proprietary drivers (see #1033).

Day 7 (the remaining half) and 8 Spent the time reviewing patches (pathfinder optimisation, rally point lines, object selection, bartering, and probably a few other things). (I've been pretty slow since I find it hard to concentrate on reviewing for long, and also I've been clearing out my backlog of tickets and SVN updates etc to read and respond to, and other distractions.) I don't like reviewing patches, but I don't like not reviewing patches . But I do like that people write patches, since it's valuable to grow the game's developer community. So I get quite conflicted... Maybe it'll help if I try explaining how I see things. Firstly, I think code quality is important to maintain. There are lots of different ways of measuring the value of code: features, bugs, performance, number of lines, readability, maintainability, cleverness, etc. The most critical measure is features - we want to write an RTS game, and if we haven't implemented the features necessary for an RTS game then we've failed. Patches that add or improve features are therefore good. The other external measures that are visible to players are bugs and performance - if either is particularly bad, then people won't have fun playing the game. The remaining measures are internal to the code and totally irrelevant to players. But all of these measures are interlinked. More features means more code, and more bugs and worse performance. Performance optimisations hurt readability and maintainability. Clever code might implement the feature with less code but be harder to read and maintain (you have to understand the cleverness before fixing bugs in it); non-clever code might be very verbose which makes it hard to read (it's easy to get lost somewhere in the middle). When code is unmaintainable, its bugs and performance problems will take a lot of effort to fix. And most features have to interact with each other, so if one feature's code is buggy or unreadable then it becomes much harder to add new features that have to interact with it. That means that when a patch adds useful features, I think we shouldn't automatically accept it, even though it'll make the game better in the short term - we need to balance that with all the other quality measures else it will cause difficulties in the longer term. In the worst case, problems in the code can seem too hard to fix and cause progress to grind to a halt. (I believe that's what happened with our pre-2009 gameplay code; the only way to make major progress was to throw it all out and start again, which was very painful.) So that's why I think it's important to spend effort on carefully reviewing patches, even if they're clearly solving a valid problem, to provide a second opinion on whether they're solving the problem in a sufficiently good-quality way and identify changes that would improve the solution. That applies especially to new contributors, who are less familiar with the existing code and conventions and typically need to rely more on the second opinion of a more experienced developer, but I think it's also worth having people read and comment on changes implemented by everyone else (possibly after they're committed to SVN) so nobody can get away with doing anything too crazy. The difficulty is that reviewing can take a lot of effort, since you've got to understand the problem, and the patch's solution, and potential alternative solutions, and explain it all clearly to the original author so they can fix it. Often that takes more effort than just solving the problem yourself, and personally I find it pretty tedious and unenjoyable, but the hope is that the review comments will be something the original author can learn from and apply to any subsequent work they do. (And hopefully the comments will really be about improving code quality, not just about applying the reviewer's insignificant personal style preferences - I think I fall into that trap too much ). (The other trap is to focus too much on the internal quality measures as a goal in themselves, when they're not what really matters. The code only needs to be maintainable enough that we can finish the game with it, and maybe do some mods or a sequel etc - any extra effort put into quality will just be wasted. I think I fall into that trap too.) Anyway, that's just my opinion

They're used for the OpenGL capabilities database, and nothing else. I've been meaning move all my stuff onto a newer server (with bigger disk and newer software) and then update that database (and update the code since the latest data triggers some bugs), but haven't got around to moving yet . But I still mean to do it, some time soonish.

I think that's not really accurate . 32-bit processors can already add 128-bit values in about one cycle (using SSE), and read data from RAM in 64-bit groups, etc. "32-bit" doesn't mean everything is limited to 32 bits - lots of stuff (especially where performance matters) is larger than that, and stays basically the same on 64-bit processors.

10 July 2009. I believe it was MarkT logged in as root on his CVS server.

Yeah, 64-bit Windows applications seem pretty rare, because it's rarely worth the cost of maintaining both 32-bit and 64-bit versions. It only really matters for applications that want to use more than about 3GB of RAM (or virtual address space). When they don't need that much (which 0 A.D. doesn't), 64-bit just provides a mixture of minor advantages and disadvantages for performance. (More CPU registers is good; SSE2-by-default is good; 64-bit arithmetic is occasionally good; bigger pointers use up more cache so they're bad). Won't make much difference either way, so it's better to spend the effort on optimising the 32-bit version of the code which'll help everyone on both 32-bit and 64-bit Windowses