Leaderboard

this is exactly what I want. If I arrive at a construction site with a stronger force I want to be able to halt progress. I can't think of any particular justification for either decision though. Are you suggesting that non siege units would never be able to take out a tower? I very strongly object to this because it is not possible to create siege until phase 3. This means if someone starts building a tower near my base it is impossible to stop the construction unless I keep guard over it and kill any units coming to do more construction work. So in my view this severely overpowers aggressive construction (which we deliberately weakened a while back by reducing armour and build rate with more workers).

I think we should decide one thing before making this decision (as the gameplay impact varies quite a lot depending on how we do other things): Should non-siege units be able to attack foundations? I could see arguments for doing things both ways, after all, if they can't the unit roles would be more clearly defined and the role of siege would be bigger. It would of course make it harder to raid though, and also a bit harder to claim as realistic. It would mean that the attacker would be forced to focus more on taking out the builders (especially early in the game), but again, that could be a good or a bad thing. Removing the ability for non-siege to attack foundations would lessen/remove some of the concerns which have been raised against tying completion % and health together, after all a tower doesn't generally provide much of a challenge to siege engines.

I'm going to try answering some questions. First, about the transparency. The transparency is handled different depending on the material used in the xml actor: If you use a material with "player_trans" means that the transparencies in the texture will show playercolor. If you use a material with "basic_trans" means that the transparencies will be handled as basic transparency, achieving the effect needed in the tank wheels. Therefore, you'll need different .xml actors in the unit. (example: main actor the hull with playercolor, and attached to it the props of the turret [also with playercolor if there's no transparent elements], and the wheels with basic transparency) To enable the normal/parallax and specular effects, you need to do the two following changes (and have a graphics card/driver with good OpenGL 2.1 support) -First, you need to make some changes on the .cfg file of the game. The best way to do this is making a new copy of the file binaries\data\config\default.cfg an rename it as local.cfg Open the file with a text editor and make the following changes: Set preferglsl=true (this enables GLSL mode) Set gentangents=true (this enables AO, normal/parallax, and specular mapping) Set materialmgr.quality=10 (value 10 to enable all the effects, 5 to enable only some of the effects, or 0 to turn them off) -Second you have to specify the correct material in the .xml actor files in order to use the effects. I've already explained the transparency differences. basic_trans_parallax_spec -> this enables "basic transparency", "normal/parallax" map and specular map (i.e for the wheels) player_trans_parallax_spec -> this is like the first, but with playercolor (i.e. for the turret and hull) player_trans_ao_parallax_spec -> this one enables the same as the above, but also "Ambient Occlusion" map (I think you don't need it because the AO is already in the diffuse texture) You can find all the material files in the folder "0AD\binaries\data\mods\public\art\materials". But I think those two first are the ones you're looking for. Final note: When specifying the texture's location in the .xml actors, you have to tell the engine which type of texture is, like the following example (not sure but I think It has to be in this order): <textures> <texture file="structural/rome_struct.png" name="baseTex"/> <texture file="structural/rome_struct_norm.png" name="normTex"/> <texture file="structural/rome_struct_spec.png" name="specTex"/> <texture file="structural/ao/rome_market_struct1.png" name="aoTex"/> </textures> For more information about the graphic options, you can follow the link that Pureon posted: http://trac.wildfiregames.com/wiki/Manual_Settings#AdvancedgraphicsGLSLonly I wish you good luck with your project!

You may not, but the crowd you'll attract will be glad to make all the unofficial campaigns you want! That's the thing about triggers. Okay, they're a requirement to make a campaign, but most of all they're a requirement for a solid community and a lot of community content. There will be a lot of silly scenarios made by inexperienced players, but there will be some really talented people making scenarios as well ... and I believe that some of these may even want to help you work on the official campaign!

Join the club, then! Haha!

A while ago we asked for donations via Pledgie to support a developer doing full-time work on the game for a month, and had a great response. I'm currently able to devote that time to the project (I've just finished a PhD, and haven't sorted out long-term employment yet and can wait a while) so I'm going to start doing that now. This isn't meant to detract from the open source development of the game - instead it's an added opportunity to tackle some of the larger problems that can benefit from more concentrated work than usual. I'll use this forum topic to record my progress, so people can see what their donations are funding and hopefully get a vaguely interesting view into the development process. Detailed technical discussions should probably go in separate topics to keep things organised, but comments are generally welcome here My current (but quite flexible) plan of tasks to focus on is: Saved game support - particularly to allow players to reconnect to a multiplayer game after a crash or network failure, since large gameplay testing sessions are often annoyingly interrupted by dropped players. Saving single-player matches is also a frequently requested feature. Better tools for measuring the game's performance. We want to optimise various aspects of performance - overall framerate, consistency of framerate (i.e. avoiding occasional pauses that make the game feel jerky), better utilisation of multi-core CPUs, etc - and I think it's worth investing in new ways of recording and analysing performance so we can improve it more effectively. Better engine support for AI scripts - mainly to increase performance in various ways, and to fix some other areas that cause pain for AI scripters. More efficient pathfinder - one of the current algorithms can perform particularly badly with large numbers of units in a small area (e.g. melee battles), and needs to be redesigned to provide much better performance in those cases. This should be enough to get started with

Day 18 I finished and committed those renderer changes (74 files changed, 2315 lines inserted, 3503 lines deleted). In general, there ought to be no visible changes. The exception is that I fixed the non-shader-based rendering mode so that its lighting matches the shader mode - the difference is that it allows the sunlight to be brighter than pure white (by a maximum factor of 2). I've also been experimenting with specular lighting, so this seems like a good opportunity to show some vaguely pretty pictures of the lighting system. (This is all very technically simple - other games have been doing this for most of a decade, but at least we're advancing a little bit.) The first component is the basic textures for models and terrain: (click images for larger higher-quality versions) Then there's the diffuse lighting - surfaces that are facing towards the sun are bright, surfaces that are perpendicular to the sun or facing away are dark: The scenario designer can control the colour and brightness of the sun, which affects this diffuse lighting. Surfaces that aren't lit directly by the sun shouldn't be totally black - they'd still be lit by light bouncing off nearby objects. As a (very rough) approximation, we add an ambient lighting component: The scenario designer can control the colour and brightness again, with separate values for terrain and for models to give them more control over the final appearance. Finally there's the shadows: All these components get multiplied and added to produce the final result: This is what the game currently looks like. If you compare it against the first image, you can see that some parts of the scene are brighter than the unlit textures - that's what happens when the ambient plus diffuse lighting is brighter than pure white. (OpenGL generally clamps colours to the range [0, 1] so you can't exceed white, so what we actually do is compute all the ambient and diffuse lighting at 50% of its desired value and then multiply everything by 2 just before drawing it onto the screen.) I also added some shader code to do specular lighting, to simulate the sun reflecting off shiny surfaces. For testing I've applied it to every model, which looks like: and that gets added to all the previous lighting so you end up with: Unlike diffuse lighting, specular depends on the position of the camera, so it looks better in motion. Also it obviously shouldn't be applied to every model, and should preferably be controlled by a new specular texture for models that want it (so e.g. the metal parts of a soldier's texture could be marked as highly reflective and the cloth parts as non-reflective), but that should be easy to add thanks to the changes I made to the renderer, and then it might allow some nicer artistic effects. Performance of fancier lighting is a potential concern, since it does extra computation (in this case a vector normalisation and an exponentiation) for every single pixel that's drawn. In practice, with specular lighting applied across an entire 1024x768 screen, the extra cost on an Intel GMA 4500MHD on Linux (which is barely fast enough to run the game decently anyway) looks to be about 2msec/frame, while on Intel HD Graphics 3000 on Windows it's too small to easily measure. So it should probably be optional to help the bottom-end hardware, but is fine for anything slightly more advanced than that.

Day 15 Worked on various minor fixes to make the pathfinding less broken, and updated the JPS A* to work with the real technical requirements (correct diagonal movement, non-point goal areas, etc), so it's nearly possible to test performance in a proper gameplay environment. Some more thoughts on JPS: Intuitively (i.e. very informally and maybe wrongly), JPS works because of two observations: * Shortest paths will wrap tightly around the corners of obstructions. (Imagine the path is a piece of string from the source to the destination, winding around various obstructions, then pull the string tight. It will get pulled until it's going in straight lines between the corners of the obstructions. If it's not already tight around the corners, it's not a shortest path.) * In a grid (only allowing horizontal/vertical/diagonal steps), when there are multiple equal-length paths between the same two points, you have to make an arbitrary choice between them, and you can always prefer the one that moves diagonally as early as possible. Therefore, if the pathfinding algorithm is extending a path in a horizontal/vertical direction, it can continue in a straight line until it reaches a corner to wrap around. If there is no corner, there's no point turning diagonally or 90 degrees from the current direction, because it would always be possible (and preferable) to have turned diagonally on an earlier step. (That continuance in a straight line is the "jump" in "JPS", and is what makes JPS a worthwhile optimisation.) If the algorithm is extending a path in a diagonal direction, it can continue in that direction; or it can turn 45 degrees and go horizontally/vertically (since that might still be a most-preferred shortest path); or it can wrap around a corner and turn 90 degrees. The definition of "corner" depends on how you define connectivity between grid cells. The original JPS paper says that any horizontally/vertically/diagonally adjacent passable cells are connected. Here's some diagrams of the shortest paths (in blue) from the red blob to every other cell, where black cells are impassable: In the second diagram, note that the paths can squeeze through the diagonal gap between the two impassable areas. That's a bit nasty because unit movement is not tile-based: units move along the path in arbitrary-length steps, and they might end up standing precisely on the impassable tiles' corners or (due to non-infinitely-precise maths) actually stand inside an impassable tile, which is bad. But we don't want to forbid diagonal movement entirely, because it allows much higher quality paths than purely horizontal/vertical movement. To fix that, we can declare that diagonal moves are only allowed between two passable cells (i, j) and (i+1, j+1) if the other two adjacent cells (i+1, j) and (i, j+1) are also passable. This means the diagonals do not connect any two cells unless they are already connected by horizontal/vertical steps (which incidentally simplifies other tasks like reachability testing). Now the shortest paths are like: This means the paths always stay at least half a tile away from the obstructions, so we won't suffer from numerical precision problems as before. Interestingly, the path around the corner in the very first diagram has two turns (from horizontal to diagonal, then to vertical), whereas in the new approach it only has one turn (from horizontal to vertical), so the new version might result in fewer processed A* nodes and work a bit faster. The changes to the original JPS algorithm are straightforward (unless I'm misunderstanding it and introducing bugs) - horizontal/vertical jump points occur one cell later, and have 2 forced neighbours instead of 1, while diagonals have no forced neighbours at all, so it just needs small tweaks to the code.

Day 14 Slow continued pathfinding work. In particular, trying to get all the parts of the game to interact correctly with the new navcell-passability concept. It's important for the design to be clear on what its concepts actually are, so this is my attempt at describing the conceptual details of what I'm trying to implement now. (I'll probably copy this as documentation on the wiki when it's cleaned up and implemented properly.) First we start with a map like this: (click image for larger and higher quality version) There's some small units, a large unit (the siege tower), a building, a fence, and some water (with steep terrain around its edges). Units are "dynamic obstructions" - they move around frequently, and they need to perform pathfinding operations, and they generally can't pass through each other. Buildings and fences are "static obstructions" - they don't move, and units can't pass through them. Dynamic obstructions have a "footprint radius", measured in high-precision units (i.e. not quantised to tiles), corresponding loosely to the graphical size of the unit. Dynamic footprints don't have a separate width vs height, nor an orientation. They don't have a precise shape - they're sort of squares, or sort of circles, or sort of neither, depending on how you look at them. Static obstructions have a square footprint with width, height, and orientation; or a circular footprint with radius. Terrain can also block units. Terrain is split into fairly large tiles, and each tile might be passable or impassable, depending on water depth, steepness, etc. Each unit belongs to a "passability class", which defines the exact limits on water depth, steepness, etc, that should be used for that unit's movement. The pathfinder uses a "navcell grid", which stores a boolean passability value for every navcell on the map, per passability class. Navcells are smaller than terrain tiles (currently there's 4x4 navcells per tile). ("Navcell" is just a term for the tiles used for navigation, to distinguish them from terrain tiles). The navcell grid is computed from terrain passability and static obstructions, like so: (click for bigger and better) Here the thin dark blue lines indicate the footprints of all obstructions. Note that the impassable cells from the large building are strictly inside its footprint shape; we take a conservative approach so that if you tell a (zero-sized) unit to walk to the building, it can walk all the way up to the footprint edge without stepping onto any impassable tiles. Unfortunately this mean the fence is invisible to the navcell grid, since it's too narrow to strictly contain any cells. We should enforce that no static obstruction footprints should be that narrow (i.e. narrower than 2*sqrt(2) navcells). The navcell grid only blocks a unit if that unit's central point enters an impassable tile (regardless of the unit's size). To cope sensibly with large units, each passability class defines a "clearance" value. Navcells within that distance of an obstruction are considered impassable. For standard units with a clearance of 1 navcell we get: For large units with a clearance of 4 navcells we get: This stops the large unit moving too close to the buildings or water. (Note that the fence now blocks some navcells. We expand the footprint shape by the clearance, and then compute which navcells are strictly contained within the expanded footprint. In contrast, terrain passability is computed with a kind of blur filter to expand the initial grid outwards by the clearance distance.) The navcell grid ignores dynamic obstructions entirely. The long-range pathfinder finds paths across the navcell grid. It allows moves from one passable navcell to another if they're horizontally or vertically adjacent (not if there's only a diagonal connection). The short-range points-of-visibility (POV) pathfinder is based on high-precision (i.e. not navcell-aligned) horizontal/vertical obstruction edges, and finds paths at arbitrary angles. It goes like: The cyan lines are the obstruction edges that the POV pathfinder will not cross. The green/yellow tiles are the long-range pathfinder's output, and the thin red line is the POV pathfinder's output, for the cavalry unit to move eastwards. For terrain and static obstructions, the POV pathfinder uses the navcell grid: it adds cyan edges around the red cells. That means a unit can move so that its central point is right up to the impassable cells, regardless of the unit's size. The clearance (used when computing the navcell grid) is what stops the unit walking too close to a building. Dynamic obstructions are not on the navcell grid, so the POV pathfinder adds a cyan square around each dynamic obstruction's footprint. To prevent units' footprints overlapping, each of those squares is expanded by the footprint radius of the unit that's moving. (When the cavalry unit moves up to the cyan line around an archer, the cavalry's footprint will touch the archer's footprint (dark blue square).) One slightly dodgy thing here is that a unit's clearance and footprint radius may not be the same. If the footprint is larger than the clearance, the unit might be able to get close enough to a static obstruction that their footprints overlap. I think that's probably not a problem, but I'm not certain yet and will need to clarify. Given those concepts, the rest of the passability-related code can (mostly) be derived: * Whenever a unit moves by a step, we have to check for collisions in case the pathfinder returned an invalid path (e.g. because the world changed since it computed the path). That means checking the movement is along a sequence of passable navcells; and that it doesn't intersect any dynamic obstruction footprints expanded by the moving unit's radius. * When a unit is spawned (e.g. from training in a building), we have to pick a valid spawn point that is on a passable navcell and isn't inside an expanded dynamic obstruction. * When deciding whether it's valid to place a new building, it doesn't really matter what we do. It's easiest to just verify that the new building's navcell shape doesn't touch any already-impassable navcells (computed with a clearance of 0) - that'll prevent it intersecting existing buildings or invalid terrain. When telling an AI where it can place a new building, we can give it a conservative approximation of that navcell grid. * When placing a building on top of units, we need to tell those units to get out of the way before starting construction. To find precisely which units are affected, we need to look at the new building's navcell shape, expanded by the clearance of each unit that might be in the way, and tell any unit standing on a to-be-impassable tile to move away. But that sounds kind of nasty to implement - ought to find a better way... * When a unit moves to a static obstruction (to gather resources, or to melee-attack, etc), we can tell the POV pathfinder to stop when it reaches the edge of a high-precision oriented square or a circle, corresponding to the building's footprint. (That avoids the problem when you tell a load of units to attack an enemy building, of having them line up in an ugly stairstep pattern corresponding to the navcell outline). But we need to guarantee that square/circle is not inside the building's impassable tiles, else units will never quite reach it. So we need to expand the static obstruction's footprint by at least the unit's clearance value to guarantee it will be reachable. (Maybe we should actually compute the unit's footprint radius plus its specified minimum attack/gather/etc range, and use that value if it's larger than the clearance, to allow more control over the behaviour without breaking that guarantee.) Hmm, I think that's about all for now.

Day 13 One of the problems with pathfinding is what to do when there is no path. That's common in normal gameplay - the player will tell a unit to walk to the middle of a lake, or to a tree inside a dense forest, or to a point on another island, or to a point inside an enemy city completely enclosed by walls. The basic A* pathfinding algorithm handles that situation very badly: it's entirely short-sighted so it won't realise the target is unreachable until it's searched through every single reachable tile in the entire map (maybe tens of thousands), which is extremely slow (maybe tens of milliseconds). On the plus side, A* is able to easily find the tile which is closest to the target and still reachable from the source, which is usually what the player wants - tell a unit to walk into a lake and it'll move to the nearby shoreline, tell it to walk into an enclosed city and it'll walk up to the wall, etc. On the minus side, A* can't do that if we add the JPS performance optimisations to it, because of boring technical details. So what we really need is a fast way to guarantee there is at least one path to the target, before telling the A* algorithm to find the best of all possible paths. If there isn't a path then we need to pick a new target that is nearby but is definitely reachable. What I've added now is this: (click for larger image) Each coloured region is a collection of cells, such that there is a path between any pair of cells in that region. See e.g. the maroon region near the top-center - a unit can move from any maroon cell to any other, but the vertical line of walls defines the edge of that region and there's a separate small light-grey region on the other side of the walls. There's no direct path from maroon cells to light-grey cells so they're detected as separate regions. This is basically the same as a flood fill in a paint program, except we prevent any region growing larger than 64x64 cells, resulting in the patchwork pattern. The size limit makes it faster to handle dynamic changes (e.g. constructing or destroying buildings) - we can throw away a 64x64 chunk of data and recompute it, instead of recomputing the entire map at once. When two regions are touching each other, there's a path from any cell in one region to any cell in the other. In this image, the white lines are linking all these adjacent regions. E.g. from the maroon region you can move to the region above, or below, or right, but not left. Now we can easily tell if there is a path between two points anywhere on the map. For each point, check which region it belongs to, and then search along those white lines to see if there's a sequence of adjacent regions connecting the points. Instead of perhaps a million cells to search through, there's maybe two hundred regions, so this can be very fast. If there isn't a path, we can easily pick a new target that there is a path to. First find every region that can be reached from the source, sort them by approximate distance from the original target, then check every cell within each reachable region until we've found the one that's precisely nearest the original target, and use that cell as the new target. After all of this, we can now run the A* algorithm as normal, but with the guarantee that the A* will never have to deal with the unreachable-target case by itself, so we avoid its worst-case performance and allow the JPS optimisations. So that's nice. This is basically the first part of the MM-Abstraction design (used by Dragon Age). But they use the high-level region graph to find actual paths, whereas I'm (currently) only using it for testing reachability. Their approach can compute non-shortest paths (potentially making units move in ways that look stupid to the player), and they have to include various hacks to minimise that problem and smooth out the paths. I think a better approach might be to use the high-level graph to compute a more accurate heuristic in the JPS-optimised A* algorithm, so that it still guarantees optimal paths but will tend to find the target in fewer steps. But that's future work and not needed at this stage. Another difference is their design tries to optimise memory usage, whereas my implementation is pretty dumb and totally unoptimised and is happy to throw dozens of megabytes of RAM at the problem. I think my next steps are to ensure everything's working correctly and consistently, and integrate it properly with the rest of the engine, and then do some performance measurements and optimisations, and then it should actually be usable.

Day 12 As mentioned previously, we need two separate pathfinders (one for planning long-range paths that avoid rivers and buildings and walls etc, and one for finding short-range diversions around other units while following the long-range paths), and there are problems (like units getting stuck) when the two pathfinders disagree on whether a unit can fit through a gap. What the game currently does is like this: (click for larger image) The grid pattern on the terrain shows the tiles (each split into 4x4 small cells). The cavalry unit has been told to walk from by the water up to the flag. The long-range pathfinder works with tiles: the red-shaded tiles are impassable (blocked by buildings or water or steep terrain), and the green- and yellow-shaded tiles are where the pathfinder has searched to find the shortest path. It's finding a path that travels through a piece of wall, because the wall is too narrow to have blocked an entire tile. The short-range pathfinder works with the cyan squares. Each building (and each tile that is blocked by water or steep terrain) has a square around it. Instead of using tiles, it moves between the corners of the squares, making sure it never crosses one of the cyan edges (since then it would collide with an obstacle). The thin red line indicates the path it's found, walking around the edges of the walls and then heading towards the flag. In this case it luckily doesn't have to diverge too much from the long-range path (which went straight through the wall) so it works okay, but in other cases the inconsistency is a problem. I've been changing it to instead look like: The long-range pathfinder is basically as before, but instead of using whole tiles it uses the small cells, so the red/green/yellow-shaded regions are a much higher resolution. That means it can fairly accurately represent small obstacles like the wall, without hugely over-estimating or under-estimating its size. The short-range pathfinder no longer uses a single square around a building(/wall/etc) - it computes the cyan edges to exactly match the boundary of the red-shaded (impassable) cells. The little yellow circles indicate corners that the path can go between. If the long-range pathfinder found a path, it's guaranteed that the short-range pathfinder will be able to find the same path (or a better one), assuming no dynamic obstacles (i.e. other units) get in the way, because they're using the same cell-based view of passability. I think that's good - it means the pathfinders now have some better correctness guarantees, and can make some simplifying assumptions (e.g. the long-range pathfinder doesn't have to worry about the short-range pathfinder moving a unit onto an impassable tile), and that makes it easier to implement optimisations to improve performance without worrying about breaking everything.

Days 10 and 11 Experimented with implementing and optimising the aforementioned JPS algorithm and some related pathfinding things. These are on the 512x512-tile Peloponnese map, with a path (shown in blue) going north around the gulf. The coloured tiles are the ones processed by the A* algorithm (in particular the red ones are on the closed list, and yellow on the open list). In the first image, the standard A* algorithm searches outwards in a roughly circular pattern from the start point, so the red tiles go a long way south, until it gets to around Plataea and heads north-west to the target. The second image, with the JPS optimisation of A*, searches a similar area but it leaves a load of tiles unexplored (white) inside that area, because it realises they're never going to be interesting tiles (there's always an equally good path that doesn't use those tiles). (The chosen path is slightly different in the two cases, but of the same length. There are lots of equally good paths and JPS always prefers one that goes diagonally as early as possible before going vertically/horizontally.) In this particular example and this particular implementation (with various optimisations and hopefully no major bugs), the standard A* takes about 6msec to compute the path, and JPS takes about 1.5msec, so it's 4 times faster. Because our terrain tiles are quite large, and might mark a passage as blocked when actually a unit could easily fit through, it may be useful to use a higher-resolution version of the map: Here it's scaled to 2048x2048 cells (i.e. 16x as many as before), so it can represent much narrower gaps. Standard A* takes about 130msec (22x slower than with the low-res map); JPS takes about 11msec (7x slower than low-res). Bumping it up again to 4096x4096, standard A* takes about 680msec (another 5x slower), JPS about 22msec (another 2x slower). The nice thing about JPS in this situation is that it doesn't care too much about the number of tiles - what matters is the number of 'corners' (in some non-technical sense) that the map contains. That means it'll depend heavily on the number of trees in the map (since each tree adds four corners that paths can wrap around), but if the number of trees remains constant then higher-res maps won't be hugely more expensive. There's two problems with my current implementations of standard A* (simplified and optimised compared to what's currently in the game) and JPS. (Warning: getting somewhat more technical now). Firstly, they assume the target of the path is a single point. In practice it might be a large square (units want to get within e.g. 1 metre of a square building in order to attack it) or a very large circle (archers want to get between minimum and maximum range of a target unit). That makes it harder to tell when the algorithm has reached the goal, and harder (or at least more computationally expensive) to compute the heuristic distance to the target. Secondly, JPS doesn't behave usefully if the target is unreachable - the standard A* can discover whichever reachable tile is closest to the target but JPS might have never looked at that tile. Reachability is a problem with the game's current pathfinder already; units are happy to try forever to reach a target that they'll never be able to, and the pathfinder is very slow at determining the target is unreachable. I think the sensible solution would be to do something like the MM-Abstraction method to precompute a graph of connected regions, then find all regions connected to the source, and then find the closest tile to the target out of all the tiles in those reachable regions. That'll help equally for standard A* and JPS. For non-point targets, I think the easiest efficient solution may be to simply swap the source and target of the path. The source is always a single point (typically the unit that's moving), so it's easy to run A* towards that point. The target may be multiple tiles, but I think it's easy to make A* start with multiple cells (just shove them all onto the algorithm's open list with g=0 at the start). So finding paths from multiple target tiles towards the single source point should be straightforward, unless I'm getting confused as to how this all works. Then it needs to be integrated with the reachability thing for the previous problem, since the target shape might be half reachable and half not. That's probably all doable; just needs some more work to actually do it. The other big problem is how to make units follow the long-range paths while avoiding dynamic obstacles (e.g. other units), and also to not constrain units to moving along tile boundaries (which would look very unnatural). Currently that's the job of the short-range points-of-visibility pathfinder, which uses the detailed obstruction geometry (squares with arbitrary (non-tile-based) location and rotation). To fix discrepancies between long and short pathfinders, it would probably be better if it used the same high-res obstruction tile map that the long pathfinder uses, and then it can add on the dynamic unit obstructions (which can have non-tile-based positions but don't support rotation) to find a usable route, with the added benefit that it will now only have to deal with perfectly horizontal/vertical lines. Alternatively, maybe it would be simpler and/or faster to reuse the tile-based A* over a short range with the dynamic obstructions added onto it (perhaps at an even higher resolution). I don't really know about that - I suppose I need to experiment a bit more. (In any case, this won't get finished before the next alpha release, so I'll have to leave it until afterwards - that's kind of annoying but I think it's worth taking the time to solve the problem properly. Got a PhD viva next week so I won't be able to concentrate on game stuff until then, but I'll try cleaning up some of the quicker problems with saved games and other bugs.)