Map Database  •  FAQ  •  RSS  •  Login

Artificial Intelligence in KaM Remake

<<

Krom

User avatar

Knights Province Developer

Posts: 3280

Joined: 09 May 2006, 22:00

KaM Skill Level: Fair

Location: Russia

Post 10 Aug 2012, 19:19

Artificial Intelligence in KaM Remake

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 :-D
- 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:
3872049.jpg
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.
0190766.jpg
You do not have the required permissions to view the files attached to this post.
Knights Province at: http://www.knightsprovince.com
KaM Remake at: http://www.kamremake.com
Original MBWR/WR2/AFC/FVR tools at: http://krom.reveur.de
<<

The Dark Lord

User avatar

King Karolus Servant

Posts: 2154

Joined: 29 Aug 2007, 22:00

KaM Skill Level: Veteran

Location: In his dark thunderstormy castle

Post 10 Aug 2012, 19:26

Re: Artificial Intelligence in KaM Remake

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'. :P 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?
<<

Shadaoe

Knight

Posts: 584

Joined: 28 Jul 2011, 22:00

Website: https://www.youtube.com/user/KaMRemake

Post 10 Aug 2012, 19:28

Re: Artificial Intelligence in KaM Remake

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

Krom

User avatar

Knights Province Developer

Posts: 3280

Joined: 09 May 2006, 22:00

KaM Skill Level: Fair

Location: Russia

Post 10 Aug 2012, 19:33

Re: Artificial Intelligence in KaM Remake

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 )
Knights Province at: http://www.knightsprovince.com
KaM Remake at: http://www.kamremake.com
Original MBWR/WR2/AFC/FVR tools at: http://krom.reveur.de
<<

The Dark Lord

User avatar

King Karolus Servant

Posts: 2154

Joined: 29 Aug 2007, 22:00

KaM Skill Level: Veteran

Location: In his dark thunderstormy castle

Post 10 Aug 2012, 19:37

Re: Artificial Intelligence in KaM Remake

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. :)
<<

Krom

User avatar

Knights Province Developer

Posts: 3280

Joined: 09 May 2006, 22:00

KaM Skill Level: Fair

Location: Russia

Post 10 Aug 2012, 19:41

Re: Artificial Intelligence in KaM Remake

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?
Knights Province at: http://www.knightsprovince.com
KaM Remake at: http://www.kamremake.com
Original MBWR/WR2/AFC/FVR tools at: http://krom.reveur.de
<<

The Dark Lord

User avatar

King Karolus Servant

Posts: 2154

Joined: 29 Aug 2007, 22:00

KaM Skill Level: Veteran

Location: In his dark thunderstormy castle

Post 10 Aug 2012, 19:49

Re: Artificial Intelligence in KaM Remake

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...
<<

Shadaoe

Knight

Posts: 584

Joined: 28 Jul 2011, 22:00

Website: https://www.youtube.com/user/KaMRemake

Post 10 Aug 2012, 19:52

Re: Artificial Intelligence in KaM Remake

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 !
<<

Krom

User avatar

Knights Province Developer

Posts: 3280

Joined: 09 May 2006, 22:00

KaM Skill Level: Fair

Location: Russia

Post 11 Aug 2012, 18:44

Re: Artificial Intelligence in KaM Remake

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
KaM 2012-08-11 15-39-34.jpg
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 :)
You do not have the required permissions to view the files attached to this post.
Knights Province at: http://www.knightsprovince.com
KaM Remake at: http://www.kamremake.com
Original MBWR/WR2/AFC/FVR tools at: http://krom.reveur.de
<<

stijn263

Woodcutter

Posts: 16

Joined: 28 Jul 2012, 10:23

Location: Netherlands

Post 11 Aug 2012, 22:39

Re: Artificial Intelligence in KaM Remake

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 :)
<<

dargonslayer

Blacksmith

Posts: 27

Joined: 23 Jul 2012, 21:02

KaM Skill Level: Fair

Location: Spijkenisse

Post 12 Aug 2012, 11:48

Re: Artificial Intelligence in KaM Remake

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

Krom

User avatar

Knights Province Developer

Posts: 3280

Joined: 09 May 2006, 22:00

KaM Skill Level: Fair

Location: Russia

Post 13 Aug 2012, 05:09

Re: Artificial Intelligence in KaM Remake

@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.
Knights Province at: http://www.knightsprovince.com
KaM Remake at: http://www.kamremake.com
Original MBWR/WR2/AFC/FVR tools at: http://krom.reveur.de
<<

Krom

User avatar

Knights Province Developer

Posts: 3280

Joined: 09 May 2006, 22:00

KaM Skill Level: Fair

Location: Russia

Post 21 Aug 2012, 05:56

Re: Artificial Intelligence in KaM Remake

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 :)
Knights Province at: http://www.knightsprovince.com
KaM Remake at: http://www.kamremake.com
Original MBWR/WR2/AFC/FVR tools at: http://krom.reveur.de
<<

Shadaoe

Knight

Posts: 584

Joined: 28 Jul 2011, 22:00

Website: https://www.youtube.com/user/KaMRemake

Post 21 Aug 2012, 09:47

Re: Artificial Intelligence in KaM Remake

Good job !
<<

Krom

User avatar

Knights Province Developer

Posts: 3280

Joined: 09 May 2006, 22:00

KaM Skill Level: Fair

Location: Russia

Post 21 Aug 2012, 09:53

Re: Artificial Intelligence in KaM Remake

Ans as soon as I announced it I've found another bug :D This one is trivial and hopefully will take no more than 1-2 days to fix :)
Knights Province at: http://www.knightsprovince.com
KaM Remake at: http://www.kamremake.com
Original MBWR/WR2/AFC/FVR tools at: http://krom.reveur.de

Return to “Feedback / Discussion”

Who is online

Users browsing this forum: No registered users and 5 guests