Improving the AI

I've noticed the following situation quite a lot:

...where the player can see the monster but the monster cannot see the player (and thus is still asleep) This is because the player FoV is calculated using Recursive Shadowcasting, and lacking a working noise model, monsters initially use a simple implementation of Bresenham's line algorithm to calculate if they are aware of the player or not.

In an ideal world, the monsters would either use a noise system or recursive shadowcasting of their own to find the player, but in the meantime, I need to think of a better way to make monsters active. I'm proposing that, for now, if a monster is in the FoV of the player, but cannot directly see the player, then that is equivalent to having direct line of sight (via Bresenham) to the player, and the monster will awaken and then move in a random direction to try and achieve direct line of sight.

And to answer some questions I've had about screen resolution, here is the main window maximised on my laptop running at 1366 x 768 and with the main display minimised, giving a tile display of 112 x 22 using Bitstream Vera Sans Mono, 11 pt. text (click to zoom in to see at full resolution):

The mininum (default) size is 900 x 730.

Sprucing up Monster AI #1

Monster behaviour in Kharne is currently pretty dumb. I'm not talking about (the not-implemented) special attacks and behaviour for each creature, but rather they will currently stand and fight even though the player is butchering them.

I've been thinking about this and I can achieve what's known in software engineering as a 'quick win' which will enchance AI considerably.

Put simply:

Allow certain monsters to flee away from the player if they are sufficiently injured. If there are other monsters visible that belong to the same ecology, then flee towards them. Else flee directly away from the player. If a fleeing monster cannot move away from the player, then it turns and fights.

Print fleeing/unfleeing messages as appropriate ("the wibbly flees!", "the wibbly turns and fights!")

Now, there is some additional subtlety I intend to code. If there is a Unique Monster within line of sight, injured monsters don't flee but instead shout something along the lines of "We will die for you, Wibbly the Doomy!"

Perhaps the opposite effect could also occur - when a Unique dies, all sentient monsters within view flee with a "Seeing its Champion dead, the wibbly runs away". Obviously this would not be a permanent fleeing, but of time-limited duration.

(cross-posted at r.g.r.d.)

AI and Melee Combat

Here is a video showing the first version of the Monster AI and Melee Combat in action. The video shows a Dwarf Warrior (the most melee-centred class) fighting creatures in the first level of the Wilderness and ends with him advancing to Level 2.

The AI routines are still slightly buggy - occasionally the positions that the Dungeon Object holds for the Monsters and the locations that the Monsters think they are at get out of sync. - this could lead to invisible monsters attacking the Player Character. I have no idea yet why that occurs, but it will need to be investigated further. Currently there is a hack in place to zap any monster that gets into this situation, but that's only a temporary fix at best. But having said that, I am pleased with progress on this, even if combat is currently horribly unbalanced (in favour of the Player Character)

Optimisation and the dangers of too-elaborate thinking.

Magellan over at Roguetemple has simultaneously stopped me acting like an idiot and in the process has reduced my calculating/refresh times by a factor of close to 100. How? By pointing out (the now obvious point!) that there is no need to recalculate the terrain costs for the pathing algorithm for every single monster.

Originally I wanted to recalculate for every monster because I had the idea fixed in my head that some monsters have different terrain costs than others (an ice-based creature in a fire-based environment for example), but there is no current need for a Giant Bat to have differing terrain costs than a Giant Rat, for example.

By this single change, the downtime between player turns due to processing is reduced; in the unfortunate (for the @) situation below the time for processing is reduced from ~60 ms to under 1 ms.

There are several other optimisations that could be achieved here as well - the relevant section of the recalculation code is as follows:

for x:= 1 to DUNGEONSIZEX do
begin
  for y:= 1 to DUNGEONSIZEY do
  begin
    if (Dungeon.Walkable[X, Y]) then
  begin
    if (Dungeon.Effects[X, Y] > 0) then Dungeon.TerrainCost[X, Y] := TC_TOUGH
      else Dungeon.TerrainCost[X, Y] := TC_NOCOST;
    end
  else
  begin
    Dungeon.TerrainCost[X, Y] := TC_IMPASSABLE;
  end;
end;
end;
Dungeon.TerrainCost[PlayerX, PlayerY] := TC_IMPASSABLE;

and then later on, whenever a monster moves:

Dungeon.Monsters[NewX, NewY] := Dungeon.Monsters[LocalMonster.X, LocalMonster.Y];
Dungeon.TerrainCost[NewX, NewY] := TC_IMPASSABLE;
Dungeon.Monsters[LocalMonster.X, LocalMonster.Y] := 0;
Dungeon.TerrainCost[LocalMonster.X, LocalMonster.Y] := TC_NOCOST;

Instead of just blindly iterating through the entire dungeon, a quick array of currently active Dungeon.walkable squares could be held elsewhere, since this does not change that often (currently only with tunneling and opening doors). One alternate solution would be to make Dungeon.Terraincosts merely calculated from Dungeon.Walkable but this would mean having to implement differential terrain costs for certain monsters in a different way.

Incidentally, I'd like to have at some point "push-past" rules to govern which monsters can push past another (as ever, the excellent Andrew Doull offers an extremely workable solution to this), and which ones can also open doors (which would necessitate a recalculation of terrain costs).

Progress Report #9: AI Mutterings

So I've started work on Monster AI. This is going to be quite a big task. And already it has me wishing for some of the functionality of C#. The reason? LINQ.

Every turn, the AI subroutine will process the list of currently active monsters on the level, determining what to do from their programmed behaviour, current condition, hatred for the player and so on. So I need to find what monsters are currently active. Initially I have to scan the entire level looking for monsters who are both alive and awake (i.e. aware of the player's presence, usually by being in line of sight or line of sound of him/her).

I started off with storing a list of monster pointers in an integer array. Of course, to get any performance out of this method, I need a quick way of determining if the monster is already active. So I just search the array. Whoops. Its an unordered basic array of integers. Searching performance is atrocious.

Being able to search through arrays as if they were a dataset,e.g.


IEnumerable query = from s in names where s.Length == 5 orderby s select s.ToUpper();

would be the answer to this. Instead, lacking such functionality, I've decided to use an additional TObjectList to store the active monsters. Monsters that awake are added to the list, and ones that are killed are removed. Its not ideal, but it does the job, and does it reasonably quick.

Which is needed as implementing pathfinding for monster movement is pretty processor intensive. I've been experimenting with the free Delphi pathfinding components available here (demo exe here) and they seem to do the job, but for every monster that wants to move towards the @ (a later enhancement I'll add is moving them towards the last known position of the @) I need to recalculate the terrain costs of the entire level, and the only way for now to do that is to iterate through the entire level one tile at a time. Delving into the source code of the components reveals that they use a TBits array in their calculations, so I'm not sure there is much more room for optimisation.

Anyway, the AI is still a work in progress - dealing with finding the correct direction to represent monsters fleeing "directly away", (for whatever reason) from the player is proving to be a pain but for now here's a video showing the beginnings of the path-finding in action:

Since no combat has been implemented yet, the monsters cannot be killed, and near the end of the video you'll notice the @ stepping onto a monster, but the basics are there and starting to shape up nicely (that sometimes the screen draw takes more than 1 ms is due to the green diagnostic messages being displayed in the message log - standard performance even with the cost of terrain calculations being performed multiple times is still below a millisecond)