What makes Knights and Merchants so good?

[harold]

That's not what I meant mate, it's good enough, but traffic jam handling is non-existent (I admit it's a tiny bit complicated, especially because of the weird requirements that A* has for the heuristic function) so I'll obviously have to do something about that :roll:

[rephikul]

Well maybe we should move it to the TKE thread but ok..

1) wouldn't choosing the least-idle serf result in only 1 serf being in use?
4) while that would "solve" traffic jams, it would make the serves take long routes in order to avoid a serf that was planning to walk somewhere but isn't even near yet. And anyway, you don't really want to avoid a crowded place where there isn't a traffic jam (for example, a 2way road where everyone walks on the right side and thus avoids a jam, but all squares can be occupied).

1) it'd result in serfs sitting around as in KAM, but your city still up and running. (mean you dont need to build more serfs until they all start working)

4) serfs should never take longer routes, but only decide which alternative it'd take cause its possible paths was already planned out when you add a building. (or at least, in the model i suggested it would work that way)

And on the 2 way road: Yep, i realized it too, but after i posted the previous post xD 2 person traveling the same way with the same speed shall never collide assuming they arent stacked to begin with. I guess then path choice now only apply on routes with 1-width streets cause you can default *walkring to the right* on any 2-width streets.

[Lewin]

Hi,
I have an idea to add to fix traffic jams, especially at the storehouse. If you have a serf inside the storehouse that wants to go out and a serf outside the storehouse that wants to go in then they should "pass in the doorway". The storehouse is one of the worse spot for traffic jams and this would fix the problem of getting 20 serfs stuck inside your storehouse with no way out because the entrance is jammed. Serfs should avoid "bumping" troops out of their positions, if there is an easy way around. Also, many people use the "cheat" so that you only have to connect roads by the corners. (because the serfs will still use it) I never do this myself and I think that unless the roads all connect by edges then it is not a valid route.
Lewin.

[The Dark Lord]

That ''cheat'' isn't all to handy. Watch this: http://img522.imageshack.us/img522/4148/unhandysi3.png

The red line shows the way serves walk if they want to bring something to the southern storehouse.

[rephikul]

Indeed, usually the missing stone would result in massive traffic jam. I think this is the only application i have for it:



As you know sometimes long roads with clear planning would help with unit flows and cutting off an intersecting might aswell being the only thing you need

[harold]

rephikul: I get the impression that you want to store the path from any building to any other building, while that would save on path-calculations it would be quickly get out of hand size-wise - and keep in mind that roads can change (bypasses are made and alternative routes emerge etc, roads can even disappear)

if that intersection works as intersection then I'll have to change A* a bit to allow the unit to walk over grass for 1 tile..

[rephikul]

rephikul: I get the impression that you want to store the path from any building to any other building, while that would save on path-calculations it would be quickly get out of hand size-wise

Yep, i prefer remembering the state of things to cut down on re-calc cost. Too bad all the projects i've done on the past have easy a* requirement so it's much easier to do, however you dont exactly have to remember path from al building to another, for instance you only need to remember path to watch tower and store house from quary. And by no mean it'd be troublesome since as things change you'd also have to update your roadmap. There's lots of hand-holding involved but if helps with performance, might as well try it out ;p

[harold]

A* isn't all that slow, and caching rarely hurts - but the cache will have to invalidate all paths as soon as any building or road changes (it'd take more time to figure out which entries to invalidate than to recalc them) and caching all paths would result in a huge cache. Also, new paths aren't needed extremely often (only once a serf wants to start walking somewhere, or when it it blocked by something it didn't expect (such as a new building)) and most individual paths are rarely used (once or twice (in rare cases thrice) for each thing the building at one end of it produces)
Btw, with "all paths" I mean "all paths that are used at least once" (not paths from barracks to mills for example)

So now I must wonder, will a cache really help? Often-used routes are generally short (usually people build chained industries near each other, such as farm->mill->baker), the cache can not get big in a town that you still build at (due to repeated invalidation), each cache miss will only take longer than if there were no cache, and the cache must clean itself on invalidation (which adds to the fragmentation of the heap)

A simulated village made by snorro uses an average of 1% CPU time once it is loaded - the village is rather small but 1% is not a lot, and it even shows the graphics (except the terrain) so my guess is that that will work out rather well (the terrain does not add considerable CPU load, most work is done on the GPU). Military troops movement will add a lot more A* calls but they cannot really be avoided with caching. Military units are often idle, fighting, or already walking though, but if they Do need a new path it's often a long one that can "explore" a lot of the map because it isn't limited to roads. Could become difficult and probably needs queueing of A* calls to spread them across multiple updates..

Will try all suggestions though.

[rephikul]

Speak of troop movement, there's this thing i really hate but dont know how to solve cause i dont have any experience with formation, that's when a squad arrive at destination it'd try to form up, and usually the formation could be done real fast with dynamic troop location however the AI usually have a set place of a particular troop within the squad and take an annoyingly large amount of time to sort it out. If this problem would be solved i'd be happy even when you use the original KAM's troop movement where everyone move parallel with the flag bearer to cut down on path calc

[Krom]

What makes KaM so good:

- realistic living world. Every unit action is reasonable and detailed (with perhaps very few simplifications).

- indirect control on economy/village. Partly indirect control on troops fighting.

- looks and music are great aswell

- overall feeling of not-so-fast gameplay, where else one mission could take 8hours

@rephikul: Yes, that is annoying, but closer to real-life where every soldier in squad knows his place. I guess instead they should act all together when re-forming to save time instead of everyone acting for itself.

[JBSnorro]

Btw, with "all paths" I mean "all paths that are used at least once" (not paths from barracks to mills for example)

Why not from the barracks to the mill? That path may be used frequently: After dropping a weapon at the barracks, his next assignment might well be picking up some flour at a local mill...
So caching routes cannot involve caching only routes that are used once, because even that number is too large. In my opinion caching can only be useful if you cach the top most frequently used routes.
But still I'd recommend A*.

@rephikul:
That problem also bothered me, so I've set up a system for getting in formation. The system optimizes by making the longest route as short as possible, in other words, the squadmemebers will stand in formation as soon as possible, ignoring the index in a squad.
That problem posed a fun challenge, but it's working now.

[harold]

So caching routes cannot involve caching only routes that are used once

Yes it can. Routes that are never used can be definition never be cached, and routes that are only used once will likely be thrown away anyway (depending on cache size of course)

only be useful if you cach the top most frequently used routes

Caching only involves the most recently used items anyway. We're talking about caching, not about trying to save all routes.

But still I'd recommend A*.

And caching does not mean that you do not have to calculate the routes - if you don't you wouldn't have anything to put in the cache anyway

Why not from the barracks to the mill? That path may be used frequently

Because in practice it won't be used frequently. It's only theoretically possible. It would require a mill next to the barracks, and also that the flour was not collected by the serf that brought the wheat for the next sack of flour. Rather unlikely. Which is why I chose it as example

[JBSnorro]

The inverse example(Mill to Barracks) would have been a perfect example because that route isn't even theoretically possible....
But do you want caching in TKE? I certainly don't

[harold]

Well I'll try it, who knows, it might give a speed-up - and if not, well, ctrl-z is not hard to find

but the reverse route could be the same, depending on the roads (it could be that there is only 1 shortest route instead of multiple shortest routes where it would find an other one first when looking from the other end)

[rephikul]

The inverse example(Mill to Barracks) would have been a perfect example because that route isn't even theoretically possible....

In actuality, with the exception of store house, i think most routes in the game are one-way ;p