Leaderboard

I have just planned a hero: // state"ress": {},"ents": {"structures.athen.civil.centre": 1},"tech": ["phase.village"]// goal"ress": {},"ents": {"units.athen.hero.iphicrates":1},"tech": []HTN: SUCCESS actions: 35, 33 msecs, iter: 247, depth: 155 op: 1, inc_resource ( wood, 50 ) op: 2, inc_resource ( food, 50 ) op: 3, inc_resource ( population, 1 ) op: 4, wait_secs ( 10 ) op: 5, train_units ( units.athen.infantry.spearman.b, 1 ) op: 6, wait_secs ( 10 ) op: 7, inc_resource ( metal, 200 ) op: 8, inc_resource ( stone, 100 ) op: 9, wait_secs ( 200 ) op: 10, inc_resource ( stone, 300 ) op: 11, inc_resource ( wood, 400 ) op: 12, wait_secs ( 600 ) op: 13, inc_resource ( wood, 350 ) op: 14, build_structures ( structures.athen.house, 5 ) op: 15, wait_secs ( 265 ) op: 16, inc_resource ( wood, 400 ) op: 17, inc_resource ( wood, 400 ) op: 18, inc_resource ( food, 800 ) op: 19, research_tech ( phase.town.athen ) op: 20, inc_resource ( wood, 400 ) op: 21, build_structures ( structures.athen.defense.tower, 4 ) op: 22, wait_secs ( 600 ) op: 23, inc_resource ( stone, 100 ) op: 24, inc_resource ( metal, 800 ) op: 25, inc_resource ( stone, 900 ) op: 26, research_tech ( phase.city.athen ) op: 27, inc_resource ( metal, 200 ) op: 28, inc_resource ( stone, 100 ) op: 29, build_structures ( structures.athen.prytaneion, 1 ) op: 30, wait_secs ( 200 ) op: 31, inc_resource ( wood, 200 ) op: 32, inc_resource ( food, 50 ) op: 33, inc_resource ( population, 1 ) op: 34, train_units ( units.athen.hero.iphicrates, 1 ) op: 35, wait_secs ( 35 )op 3 + 33 look strange. The planner called about 250 methods and tree search depth was 155. I think, I rewrite some recursive parts where tail optimization doesn't work, 33 msecs are too much. Check it out: http://noiv.pythonanywhere.com/agentx/0ad/explorer/hannibal.html (FF30 mandatory, click GO) Edit: if you click stress with 10 loops, it shows stats from the triple store cache. Now, after clicking more often it takes only 13 msecs, much better.

WIP fix of the viking longboat ingame.

I tried to do some kind of commentary on two players playing a short match. I did this by having two other players and deleting all my units and buildings so that I can see the whole map. There is a small but thriving community in the multiplayer lobby. I recognize most of the people that go online and have probably battled against every one of them. Perhaps next time I should try to comment a 2v2.

@Teiresias { isVictorious : true }, that's the plan to become a pro. No seriously, can't run this goal every second.In a RTS a bot has to re-evaluate plans after any incident, e.g. the building needed to advance to phase.town was destroyed in the meantime. I'll use the planner to feed the economy and advance from phase to phase. Attack plans are the holy grail of planning, but during combat only a few msecs can be spared for the planner. I don't know how far I get this. Current state of thinking looks like this: I'll give you some numbers about combinatoric explosion when planning heroes works. Athen uses about 70 templates and 40 techs/pairs. Going from zero to hero, may involve max 10 levels, not that bad. The triple store searches 500,000 node/edge combinations in less than 1 msec. The trick with JS is finding the sweet spot, where IonMonkey kicks in and compiles very fast code. Then you can do amazing things. > How do you set up the various operations for the planner - by hand or do you plan on parsing the entity templates (more or less) automatically? At game start all knowledge (template, techs) goes into the triple store, here is an example where I check and resolve the requirements for a phase, name === 'phase.town', buildings stores countable buildings and entities the ents in the state. if (tech.requires && tech.requires.class){ // check for enough buildings klass = tech.requires.class; amount = tech.requires.number; buildings = H.QRY(klass + " CONTAIN") .map(node => node.name) .filter(name => ( !name.contains("palisade") || !name.contains("field") || !name.contains("wall") || !name.contains("civil.centre") )); entities = H.attribs(state.ents); inter = H.intersect(buildings, entities); have = inter.reduce((a, => state.ents[a] + state.ents[b], 0); diff = amount - have; if (diff > 0){ if (name.contains('phase.town'){ house = H.QRY("house CONTAIN").first().name; } else (name.contains'phase.city'){ house = H.QRY("defensetower CONTAIN").first().name; } return [['produce', house, diff]]; }}A H.QRY with CONTAIN retrieves templates from a given class. If buildings are missing, this section composes and returns a new task for the planner, I'm sure you get the idea if you look how the produce function works: https://github.com/noiv/Hannibal/blob/master/htn-methods.js#L145

Hi there. I'm MattFox and I am an eager young programmer willing to dive into the 0AD project. (Ok, not that young anymore, don't remind me of that ) I pretty much want to add myself to the growing list of people who tried to improve / rewrite the pathfinding - and failed. Before I accept defeat though, I want to use this thread to document my progress (and thus give me an incentive to keep working because you will certainly all love what I want to do ). ------ Navigation Meshes are a way to represent the information needed for pathfinding. They can be as detailed as one wishes and are not bound to right angles or parallel alignments, so that it is possible to create obstructions of any orientation and complexity. In complex surroundings (eg in a settlement) they adaptively refine while only minimal amount of information is stored (and explored by the A* algorithm) for large monotone areas (eg open fields or lakes). Basically NavMeshes are the way to go for pathfinding. If you have never heard of them checkout http://udn.epicgames...hReference.html and if you really want to know how all that stuff works read this master thesis http://skatgame.net/...demyen_2006.pdf . ------ For another project of mine I have already written some basic navigation using NavMeshes with rectangular Navigation Cells that adaptively grow / subdivide as the world changes. I am willing to put that code under the GPL and will thus try to integrate it into the 0ad project. It will give me an estimate of how much better (and faster) it is than the current pathfinding. Unfortunately it will be necessary to switch to arbitrary polygons (or triangles) to allow buildings and other obstructions to be placed in arbitrary angles relative to the coordinate axes. The pathfinding works almost identically, but I will need to redesign the joining / intersection of Cells. The algorithm needs some tweaks to allow units with non-zero radius to avoid corners and not bump into them (yes, it is simply done live during the algorithm. no changes of any datastructures needed). Things like checking whether it is possible to place a building at a specific position will fall of trivially once the NavMesh is implemented. Initial tests Use my already existing code to replace the current pathfinding on a grid. It will only create rectangular NavCells (of arbitrary size, depending on the enviroment) but is thus the simplest replacement at the moment and will give me some outlook of how much faster it is compared to other already existing implementations. Minor tweaks Things that can be included very easily are e.g.: keeping track of the connected components in the navigation graph to instantly return from an impossible navigation attempt (trying to find a path to a point that can never be reached is the worst case of A*); check whether it is possible to place a building at a given position (don't know where and how it is done at the moment)... (etc?) Allowing units of non-zero radius This step will need some tweaking of the algorithm but should then be able to correctly navigate units with circular bounding zones around any obstacle. Change to arbitrary polygons To befit the arbitrary orientation of buildings in 0ad it will be necessary to allow arbitrary (or only triangular) convex polygons as basis to span the entire map with as little polygons as possible. This step will remove any inaccuracy due to discretisations as they can be seen in the current pathfinding (buildings will have their exact form blocked, and not some covering of them in some grid). This will also get rid of any "recalculations of the grid" as they seem to be necessary at the moment. (Modifying the NavMesh is almost trivial and can be done live. Only checking for connected components can be a bit more tricky and should probably be delegated to a seperate thread.) The fourth step will probably take the most time. Let's see how far I will get =) At some point I also want to dive into the close-range navigation as the NavMeshes can (and should) be used there as well and I have some additional ideas regarding formations etc.. ------ That is it for the moment. I am still stuck at step 0: understanding the current codebase. Hopefully I will soon be able to present to you the first results of step 1

it may be cruel (by modern standards) but it's a fact. and besides, an actual brutal human sacrifice wouldn't be shown: the units are just sent to the altar and disappear, giving you favor in exchange

Good discussion. Though, Alpha123 and I are going to do a major rebalance for Alpha 17 (soon after Alpha 16 is released). This rebalance will address many of the concerns raised here and hopefully prepare the units for the inclusion of real formation fighting and things like charging and flanking. The huge emphasis on ranged units will be alleviated and cavalry will be more interesting. Hard counters, like Swordsmen 2x vs. Spearmen and the like will be reduced or eliminated in some cases and we will rely more on mechanics like cost, speed, attack vs. armor, flanking, etc.

Great discussion. Bots are listening...

Here is a boat, (The Last of the PDF) and the shield variations, in it since they will be needed when adding shields to boat. VikingBoat.7z

I am referring to Alpha 15. On the note of skirmishers countering swordsmen, that is problematic. The faster swordsman champions of the Athenians and Spartans were primarily used as countermeasures against skirmishers, so that is a poor choice. On the other hand, swordsmen should not be the primarily meant for countering spearmen. They should be the more versatile infantry when compared to spearmen. The advantages they should have would be made by faster speed and and lower flank penalties. Generally archers and cavalry should be the way to combat them, but giving a bonus would be unnecessary since the advantage of swordsmen should be their flexibility.

If you could hepha, check my spelling with my toolkit would be great help in your spare time

It's not enabled in our engine currently, but I think this should be enough to enable it:

Thank you for your inspiration. > asm.js tldr: forget it. Funny story. If I test in browser 0AD's handwritten cos function is as fast as the JS internal!!, cos with asm is 10 times slower AND interestingly if I remove the 'use asm' line the cos is comparable. Ontop there is a huge lag, if one calls into or out of ASM, so you are forced to write all your code in the asm module. However, then it is like writing assembler and a lot of JS feature are gone. So the only way seems to be writing Hannibal in usual JS and transpile it into asm.js. I postponed that until Alpha 517. > walls A must. Have you ever survived a MP without walls? Well, don't mean your 4 years old sister. Look here: http://www.cse.lehigh.edu/~munoz/CSE497/classes/Patrick2.ppt I think the challenge is not building the wall, but finding/logging a path through a map full of trees.

I made some trees variations for Asian Mods The base model is the carrob tree. I just provided the leaf textures. Japan_Cherry_Tree.7z

Looking good. To avoid the worst case of A*, you'll have to do some simple heuristics like described before. An iterative flood-fill method should be pretty fast and do the trick. Running some tests with my own A* setup on reasonably complex map layouts, a 48x48 (2304 tiles) can take around ~1500 iterations to cover the map, while a 512x512 (262144) can have over 88700 iterations per A* search query. If you can reduce the number of cells tenfold from a 256x256 map (~65k -> ~6k), you'd already cut down the number iterations by a huge amount, to somewhere around ~5000 for the whole map. Looks like a huge algorithmic victory to be gained regardless

Hmm, I'm not sure the constant overheads are entirely negligible. E.g. if you're doing a Starcraft 2 style triangular navmesh, each triangular cell has 3 neighbours, and you might store those as 3 pointers, which is 24 bytes per cell (on x86_64), whereas square grids require 0 bytes to represent neighbours (you just compute them with pointer arithmetic), so it'll use up some more cache space. Or e.g. you probably want to store the unexplored/open/closed status for each cell, and you need to reset them all to 'unexplored' before starting a new path computation - if you've got a square grid then you can have a separate array of those status flags and initialise it to 0 easily, whereas I think it's trickier to do it efficiently if you've got an arbitrary graph of cells. (That initialisation can be a non-trivial cost if you're doing a lot of very short paths). So I think there's some extra cost per cell and the question is how well the reduction in cell count outweighs that. ...I'm not really convincing myself that those are insurmountable problems, though

We won't need any special treatment of enemies in the pathfinder. The hypothetical new "CollisionManager" would detect collisions and decides whether to start fighting (collide with enemy), pushing (collide with friendly), or try to find a path around the friend/foe (disengage from fights).

I agree. One tiny comment though to: In case the attack range of the ordered unit is smaller than the minimum distance reachable it might me better to minimize finalDistance / pathLength. The player might not want a unit to walk around a big obstruction (like mountains or forests) for nothing. On the other hand this could be seen as a case where "babysitting" units might be acceptable.

IMO we shouldn't drop ARB support at all unless someone is really overhauling the rendering engine in such a way that supporting both is too much of an obstacle (not simply an inconvenience). I don't think that is likely, but we can cross that bridge when we get there. The way to proceed with GLSL is to clean up its existing code, make sure we detect GLSL support properly (not a config option), begin enabling it on supported systems and noting which drivers and GPUs have GLSL support but perform poorly or are buggy, and fall back to ARB on those systems, the kind of thing we already do in HWDetect.