Knights and Merchants.net Forum

Some general outlines:

- AI consists of 2 big pieces - Mayor (entity that build town and trains citizens) and General (entity that does defenses and army command).
- Mayor is flexibly scripted to build houses in certain order and counts, but they do depend on AI settings and situation
- Mayor has a CityPlanner module by its command. This module receives request to find a place for house and pics the best spot (somewhat randomly)
- AI is planned to have a set of random properties (they will be scriptable) that determine its character (Strong, Wood/Iron warfare, Speed, Defensive/Offensive). In next demo they will be assigned randomly - so each AI can be quite different from the other.
- AI will cheat, but the cheating will be scriptable as well. At minimum level AI will cheat only to avoid stucking without stone to build Quarry for example. At highest cheat level - AI will have just unlimited resources and stamp out armies
- General first impulse will be to set up defenses (although it can be an option later on, maybe rusher AI is fun too)
- To build defences General needs to find best places for them. Best tactic here is to defend at narrow passages.
- Passages will be found by using NavMesh. Building NavMesh over KaM maps is work-in-progress now ..

Ideal defense places are marked on this map by hand. Note that they all go between natural obstacles: Building NavMesh is a long process. Step one is to scan the map and detect all the obstacles. Step two - simplify shapes. The more general NavMesh is - the easier is to use it.

Hmm, you're talking about cheat levels - should I consider this as setting the difficulty for AI players?
As I've said in the chat I'm really fond of AI personalities. In C&C3 you had personalities like 'Turtle' and 'Steamroller'. I'm sure we could come up with some great names that suit KaM.
So just to be sure - will we be able to set the AI personality?

AI personnalities are great, I already saw them randomly and it looks good :p

You will have control over several AI options:
Strongness controls how much stuff AI builds (Weak AI build 2 quarries, Strong - 4)
Speed controls how many workers AI has and how many houses he can build at once, also delay between houses
WeaponChoice sets which kind of army AI prefers, Wooden or Iron (if allowed)
Defence/Offence - thats obvious

Maybe we add some more controls. Some are on-off kind, some are percentage. Maybe with combination of these you can setup a sort of personality?
Of course when time comes we could add more options, e.g. food choice or ability to attack from behind, who knows )

That's all great, but if you set all those things the AI can't surprise you because you know what it's going to do. I think only two parameters are required: difficulty and personality.
Strongness and speed = difficulty
And type of weapons/tactic depends on the personality.

Detailed parameters setup is for MapEditor, so you could setup your SP map to be challenging (make 2 strong expansive enemies with half prebuild towns and 1 weak ally you need to defend).
Difficulty - maybe, but not sure in what bounds.. we'll see about that later.

Personality is hard to express in Mayor, maybe when we do General we can think of traits for him. Which traits would you suggest?

Ah okay, I thought you were talking about settings for setting up a game in the multiplayer lobby for example.

I think personality should be expressed both in Mayor and General:
Possibilities for Mayor:
- Leather or iron
- Mass wood
- Tower rush
- Defences or no defences (for very agressive personalities)

Possibilities for General:
- Rush (as soon as peace time is over, an (all-in) attack?)
- Defensive gameplay
- Map control gameplay (securing resources for long games, locking players up in their town by securing the exits)
- Sneaky gameplay (attacking from multiple directions, trying to flank, et cetera)

And more...

I think that with all the settings TDL pointed out (and even more :p), we could have a quite good control over the personalities :p And that'd be really great !

Spent whole day today optimizing and debugging navmesh builder .. you would not believe how many tiny details are there to code.

1. Calculate Terrain passability (readymade)
2. Use marching squares algo to get all obstacles in vector form.
3. Throw away obstacles smaller than 5 tiles as nonimportant
4. Clean up shapes and throw away points that are in positioned in straight lines.
5. Apply Douglas-Peucker algo to simplify obstacle outlines (splitting each in halves cos DP works for lines, not loops and also keeping points on map boundaries)
6. Check if outlines are non self intersecting and reapply DP with more precision if they are
7. Check if outlines are not degenerate and again reapply DP with more precision if they are
8. Now, readd more nodes to long lines for better triangulation later on
9. Setup Delaunay restricting rectangle (original algo used supetriangle, but superrectangle works better for KaM)
10. Start pumping obstacle outlines to Delaunay
11. Add some more points in empty areas and along map borders
12. Perform Constrained Delaunay Triangulation
13. As with every step - make sure we get data back and ready for debug renderer, so to check by eye if all is correct
14. Take CDT results and swap triangles so that they meet obstacle outlines (mentioned below bug is here)
14a. Detect all intersections and cut their triangles
14b. Clip duplicate edges and assemble two outlines for polygons left and right to the edge
14c. Triangulate them anew
15. Throw out supporting frame triangles
16. Throw out triangles within obstacles (yet imperfect)
17. Check out resulting map if it did not crashed till now xD
There are still few critical flaws - algo does not handles polygon triangulation well. That causes crashes on certain maps like Alcatraz which have quite sophisticated passages. I guess it will take another day to sort out .. Then I could start planning navmesh usage (how to parse it, what data to cache and what to calculate)

All in all I'm feeling very tired, yet confident, that piece by piece final result will be reached

Hehe, I know the feeling. Did you do ALL these steps today though? That's extremely impressive. Delaunay triangulation alone would probably take me half a day already.

The picture looks very promising already. Like you said, this has potential in the path finding business

It looks very nice and promising
I cant wait to see more

@stijn263: I've been busy with this for a week now, googling about it, stitching and filing the pieces together, bugfixing.
Step 14 was fixed on Saturday. Now there are bugs with collinear obstacle outlines generated in step 5, That will take another few days I guess.

I took Delaunay code from the web (it has credits on top of PAS file), but had to do a face-lift to it to adapt to KaM square maps. Original code used supertriangle approach.

NavMesh is complete

I've fixed all of the found bugs in triangulation and shape simplification functions. Had to use a special test that loads and generated navmeshes for all KaM maps in Remake (180 including debug ones), all maps passed the test.

Now comes the hard part - figuring out how to use it

Good job !

Ans as soon as I announced it I've found another bug This one is trivial and hopefully will take no more than 1-2 days to fix