Official KaM Remake Bugs topic

[Piko]

Yeah, but serf look younger than laborer, and laborer's voice sounds younger than serf's... That why I think it should be changed.

[Da Revolution]

beards make people look older.

[Lewin]

Yeah, but serf look younger than laborer, and laborer's voice sounds younger than serf's... That why I think it should be changed.

Hold on, before you said this:

Ok, I found small bug: in Polish languige (propably) serf have laborer's voice, and vice versa. This should be fixed.

Hmmmm your story is not very consistent...

If it's always been that way, I don't think we'll change it just because of guessing the age based on a face that is only made of about 9 pixels Also, in English the labourer (knight) sounds older than the serf (militia). Making it different between languages just doesn't seem worth the bother when it's always been this way. And changing it will no doubt confuse people a lot.

[Piko]

Hmm... It isn't possible to change voices only in Polish languige? For me, serf's Polish voice sounds really oddly.

[GreatWhiteBear]

lets change the voices just for you

[Lewin]

Hmm... It isn't possible to change voices only in Polish languige? For me, serf's Polish voice sounds really oddly.

Most things are possible because we wrote it all ourselves. The point here is that the voices have ALWAYS been that way and people will associate that voice with the character. It will be confusing to swap it now. (the voices give each character a personality, at least in English they do)

If lots of Polish players had asked us to change it then we'd consider it, but this is the first time anybody has mentioned it, so I guess all the other players think it's good the way it is.

[pawel95]

I´m playing the game with polish/german voices and i think it is great, how it is.
That is the classical KaM feeling, like Lewin said.

[Piko]

Ok, You propably are right.

[stijn263]

Hello everyone,

I'm new here. I recently found this KaM remake, and I must say it's really done extremely well. Very nice job! Yesterday I played my first 3 player ffa lan game
Anyhow, the reason I'm posting here is that I noticed that sending a group of units all the way across the map is sometimes a bit slow (a known issue probably), however I have an idea to overcome this:

Whereas the original K&M only calculated the shortest path for the leader, you decided to calculate the shortest path for each individual unit: one of the many improvements! With my discrete mathematics and mathematical programming background I spent days thinking of an efficient algorithm for this special case of a multiple shortest path problem, but I couldn't think of any algorithmic improvement. However, having the original game in mind, I came up with a different approach:

First, calculate the shortest path for the leader and have all units copy this path like in the original game (this'll take little time I assume) Next, calculate the shortest paths for the other units one by one in a second thread. As soon as the path for a unit is calculated, it stops following the leader and starts taking his own path. For short distance or small groups you won't notice any differences with the current situation. However for large groups and a long distance, you will see each unit following the leader for a couple of seconds first and only then take a different route. This is of course suboptimal but it has a huge advantage: The game will keep its flow!

Please tell me what you think of my idea

Greetings, Stijn263

PS: I couldn't resist and did a complete subversion checkout of the source code, and, although my Delphi knowledge is limited, I must say that you guys work well structured, keep it up!

[Lewin]

Hello Stijn263,
Thanks for your post

Yes it is a known problem and we appreciate your ideas on the matter. We rely heavily on determinism to keep multiplayer in sync and for replays, so any solution to this problem has to be deterministic, and not depend on e.g. how long it takes for another thread to process something. However your solution is still viable, you just need to "guess" how long the thread will take and then get the response from it after that many game ticks. If it's not done after that time we wait for it. If it's ready before that time, we still wait because otherwise it breaks the determinism. So we could always allow the pathfinding thread say 10 ticks (1 second on normal speed) and then get the response from it after that time.

So when you order a group to move, the leader calculates his route, and the group members spawn off pathfinding threads to calculate their route, and set a count down to fetch the calculated route from the thread after some amount of time and start walking it.

There's only one problem I see with that, what does the unit do in the time before the route is ready to walk? If he just sits still, the game will feel unresponsive. If he starts off in some guessed direction, then he won't be positioned at the start of the route being calculated so we'll have to somehow adjust the route when it it returned from the thread to compensate for the fact that we have moved (although we probably only moved 1 tile so I guess it's no big deal).
Let me know if you have any thoughts on this.

We've been planning for a long time to refactor our warrior code into a new class for a "group" (currently all group related code is managed by the leader of the group, just an ordinary warrior class) so this change would fit in well after we've that, because currently the warrior code is pretty hard to work with.

There's another problem with pathfinding for groups that you might be able to help with: If you order a group to go around a mountain, they all take the shortest route, right next to the mountain. This means they all want to march in a single file line, but that's much slower/less efficient than walking side-by-side (this is why the AI always attacks you in a single file line in KaM). Someone suggested some kind of "swarm" algorithm to solve this. I guess just preferring to not step on someone else's route would be a good start, but I can't think of how to make that efficient...
If you have any ideas about that we'd be very interested to hear them!

PS: I couldn't resist and did a complete subversion checkout of the source code, and, although my Delphi knowledge is limited, I must say that you guys work well structured, keep it up!

Thanks! On a project this size structure is essential otherwise the code would be buggy and impossible to manage. Thankfully Krom is very good at managing structure and refactoring code to make it neater and more according to object oriented programming ideals. Without his efforts the code would be a real mess (plus the project would never have been started in the first place!)
Cheers,
Lewin.

[stijn263]

Thank you for your response and being open towards new ideas.

Yeah, I knew you used simultaneous simulations for multiplayer, but I didn't fully realize the consequences. I read 1500 Archers on a 28.8 Network Programming in Age of Empires and Beyond. It is a very interesting approach. However this makes multithreading a bit harder I think, because it is very easy to introduce out-of-sync errors and it is more difficult to debug.. Although I suggested using two threads, it is also possible using just one thread, the idea is still the same:
Instead of calculating all paths at once, calculate only x paths per y ticks. Until a unit is given to the shortest path algorithm, use a guessed direction.

If he starts off in some guessed direction, then he won't be positioned at the start of the route being calculated so we'll have to somehow adjust the route when it it returned from the thread to compensate for the fact that we have moved (although we probably only moved 1 tile so I guess it's no big deal).

Ah, yes I assumed calculating the path for 1 unit would not take longer than the time it takes him to move to more than 1 tile. Is that correct? The shortest path calculations for the units are done sequential using their current position (not their original).

There's another problem with pathfinding for groups that you might be able to help with: If you order a group to go around a mountain, they all take the shortest route, right next to the mountain. This means they all want to march in a single file line, but that's much slower/less efficient than walking side-by-side (this is why the AI always attacks you in a single file line in KaM). Someone suggested some kind of "swarm" algorithm to solve this. I guess just preferring to not step on someone else's route would be a good start, but I can't think of how to make that efficient...
If you have any ideas about that we'd be very interested to hear them!

I'll give it a thought, interesting problem.

One question: Did you (and if so, how?) tailor your shortest path algorithm to this special subclass of graphs? (If I recall it correctly, it's called a lattice graph)

[The Dark Lord]

Not that I have any knowledge of programming, but what about short 'breaks' while marching towards the enemy? Just a few seconds waiting time after every 20 tiles might be enough. It's not ideal but it sounds like an easy way to improve this.

[Lewin]

Simultaneous simulations has many advantages such as low network traffic, copes fine with high latency, tiny replay files that can replay the entire game, and it's fairly simple to implement once you have a seeded deterministic random number generator. Multithreading is a little bit harder but it's usually quite challenging to break a program up into separate tasks anyway. Debugging is actually easier because you can guarantee exactly the same thing will happen each time you play the mission. When something becomes out of sync you can detect which tick it happened on then replay that tick stepping the debugger through the entire game until you find where it goes out of sync. It's actually not that easy to introduce out-of-sync errors once you have your system set up, any user input that effects the simulation is funnelled through our GameInputProcess which automatically stores and sends it to other players. The UpdateState aspects of the game are all written deterministically and use our own random number generator. Once you get the idea it's pretty easy. We haven't had any out-of-sync errors in 10 months or so, over 18 years of multiplayer games
To be honest I can't think of another way to write a network system for an RTS which wouldn't require a huge amount of network traffic or be very complicated to code, although I guess there are other methods.

Yes the path finding could definitely be calculated in less time than it takes to take a step so that wouldn't be a problem, you're right

I think we could do it with threads as you originally suggested, but in a deterministic way by waiting a fixed time rather than for the thread to be finished.

Our shortest path algorithm (we call it path finding) uses A*, (A-Star) search for it on Wikipedia, there's an animated GIF showing how it works. I've heard it's commonly used in games. It's very much like Dijkstra's algorithm (GIF) but it checks the closest tiles first, (so it feels out in a straight line to the target until it hits an obstacle, then it feels around it always searching for the closet tile to the target) whereas Dijkstra's just does all the tiles in sequential order so it takes longer. This is nice because we can give different weights to each tile, for example we've made it so tiles with a unit are weighted higher than empty tiles so serfs avoid walking along busy routes and favour less busy roads.


@The Dark Lord:
Unfortunately you cannot calculate the route in small pieces, you have to calculate the whole thing at once otherwise you don't know which way to go. For example you could guess that the best way to walk would be straight towards the target, but you might actually have to go backwards and around a large obstacle. There's no way to know this until you've calculated the entire route from the start to the end.
But thanks for the suggestion

[FeyBart]

Couldn't you make it so, that it first does the route for the leader, so the other units'll follow that, then calculate each individuals route, and lastly checks what it needs to do in order to adjust the current route to the calculated route?

EDIT:

(...)
Our shortest path algorithm (we call it path finding) uses A*, (A-Star) search for it on Wikipedia, there's an animated GIF showing how it works. I've heard it's commonly used in games. It's very much like Dijkstra's algorithm (GIF) but it checks the closest tiles first, (so it feels out in a straight line to the target until it hits an obstacle, then it feels around it always searching for the closet tile to the target) whereas Dijkstra's just does all the tiles in sequential order so it takes longer. This is nice because we can give different weights to each tile, for example we've made it so tiles with a unit are weighted higher than empty tiles so serfs avoid walking along busy routes and favour less busy roads.
(...)

Interesting. I see that your route is much more effecient. You guys really think about every little detail, don't ya?

[stijn263]

To be honest I can't think of another way to write a network system for an RTS which wouldn't require a huge amount of network traffic or be very complicated to code, although I guess there are other methods.

To be honest I never thought of how to code a network system

A* is a neat little optimization for Dijkstra, however it doesn't exploit the fact that a path in a K&M map can usually be described by at most 20 diagonal, horizontal and/or vertical lines. (in the original game that is, the different tile weights complicate matters a bit) I think that property can be used to find paths faster. I'll try and find some time this week to work it out