AI

Some words on the AIs in Rogue Survivor. 

Constraints
A strong design choice was to have a lot of NPCs (non-player character) running around. I wanted chaos and interaction. 100+ NPCs on maps is the norm in RS. A lot of NPCs are updated almost each turn. Roguelikes are fast paced games and it is not acceptable to wait 1 second between turns because the 100 fancy AIs use A*, reinforcement learning and whatnot. I also wanted zombies to behave like zombies, and citizens to behave like citizens.
To sum up:

• Fast processing.
• Recognizable and typical behaviors.

Past Experiences with implementing AIs in games
In other game projects I tried to used fancy stuff like Genetic Algorithms, Neural Networks, Planning etc..
Problem is they don't really work or are overkill and you have little control on the decision process. I read a bunch of game AI papers. Most of the time AI researchers are using complex techniques to evolve or design simple pacman-level AIs. So much effort for -excuse me- so ridiculous results.
I had much better results with very simple rule-based AIs and it is faster too. Interesting AI doesn't necessary need complex AI. Note I did say interesting not good. It's a game, you want interesting and amusing NPCs, not competitive NPCs.
Lesson learned. KISS : Keep It Simple Stupid.

Basic algorithm

Straightforward rule-based stuff, not even a FSM and not even an AI engine.

1. Sense the environement with Sensors.
2. Scan a list of rules (trigger -> Behavior) until a behavior propose a valid action.
3. Execute the proposed Action.

That's it. The "intelligence" resides in :

• the use of the Sensors  : they interpret the environement into useful percepts.
• the relative complexity of the Behaviors : they might check for additional conditions or call other Behaviors.
• the ordering of the rules : do this (eg: flee the zombie) instead of that (eg: try to get the item next to the zombie) and the NPC will appear to be clever.

Example AI : CivilianAI (actual code screenshots)
AI used by the hopeless citizens roaming the streets.
They try to survive just like you and they currently have 16 rules to do so.

From the most important one:

...To the least important one:

Some rules are more complex, using percepts computed by the sensor and apply filter on them to get only revelant data.
For instance:

BehaviorGrabItem is more complex too, it checks additional stuff on item, in particular if the NPC really want this item:

Conclusion
So as you can see it's not rocket science. Behaviors and rules aren't even objects, there is no rule engine etc...
But it gets the job done quickly both for me and the player. Those AIs are going to die anyway, and probably out of the player sight, so do you really need fancy stuff? I think not.
Would I do the same for my next game? Yes sir! The only change I would consider is encapsulating behaviors and rules into objects, and better algorithms (A*  pathfinding...) if I can allocate more CPU time.

End of post.

Building your own little fort

Mobile barricades
Barricading isn't limited to the "barricade" action on doors and windows.
You can make your own mobile barricades by pushing stuff around.
Shopshelves are very good for this.

Barricading shops
You can make your own little forts very easily.
 Some examples.

A simple "wall" setup (shown locked from the inside).

A slightly better one, to prevent zombies from seing who is inside (shown open from the outside).

A better one, with a "mobile door" (shown here closed from the outside) :

Barricading streets
Since you can push stuff around why not barricade the street to make it even safer?

This is not new, you can do all this in alpha 2.0.
Incidently, some of these screens show a new 2.1 feature I didn't mention...

End of post.

Alpha 2.1 progress

New features : followers orders, scoring, ranged weapon efficient range and the secret feature.
New options.
New content : items, enemies (both livings and undeads), skills, events and musics.
Improved civilian AIs.
Improved UI : got rid of look and inventory mode, more mouse oriented. 
And of course fixed bugs.

Rebalanced a bunch of stuff. The idea being more actions, more dangers, more stuff happens and more stuff to do.
Some changes will be visible only after some days have passed. So if you survive long enough there is a chance you'll see something new. I won't spoil anything, the secret feature and others stuff  are revealed as you play the game.

90% done and considering adding one feature (trap those zombies) before release.

I'll take time to playtest, 2.1 should be out in one week.
There are still major features not done yet, so still alpha.

End of post.

New video, public alpha in the works and rogueliketemple

New video
With music. http://www.youtube.com/watch?v=5xxYOG_NUsk
The video size inflates fast with audio recording so I had to make it very short.
Shows Intro music and Followers. 

Public Alpha (sic)
I will release soon a public alpha. I would like some early feedback, while I can still change some major stuff.

Roguelike Temple
Registered there. Seems like a nice place.
http://www.roguetemple.com/

End of post.

Alpha gameplay video

Created a youtube account and posted a gameplay video there.
Video : http://www.youtube.com/watch?v=lcIumH9_gWc
Channel: http://www.youtube.com/user/roguedjack

Shows new features like Barricading, Trading, Firearms, Leveling up and Skills.


End of post.

changelog

Change is good. Let's log it.


Alpha - April 15 2010 build
---------------------------
new Feature - Inflicting HP damage now cause damage to STA too.
new UI      - Quit game asks for a confirmation.
mod Items   - Baseball bat +4a/+3d instead of +3a/+4d.
new Feature - Progressive Day/Night phases, with gradual FoV penalty.
new UI      - Game now announces Day/night phases.
new Feature - Actors with ability CanZombifyKilled now also regen HPs from the damage they inflict on livings.
new Feature - Trading : people chat with each other to exchange items (my item vs yours, deal yes/no). The player has to initiate trade with Ais (as to not get spammed by Ais offers).
new AI      - BehaviorEquipWeapon: equips weapon from inventory if none equiped (used by Civilian AI).
new AI      - BehaviorRestIfTired: wait if tired (used by Civilian AI).
new UI      - Icon for actors who can actually trade with the player, so the player don't waste time with useless trade demands.
mod Data    - changed Item.Quantity from int to short for memory and consistency.
mod AI      - Zombies AI now chase visible enemies first.
fix Rules   - Fixed an awfull typo-induced bug in isAdjacent(). Mistaking a X for a Y gives funny results...
new UI      - When upgrade time, added a popup on top of screen like other modes to make it more noticable.


End of post.

Map class: Array & List+Hash

A short presentation about using List+Hash instead of Arrays.
Confirmed programmers can skip this one but I thought it might be quite usefull for novices.
Non-programmers can skip this large nonsense post.

- Good Array

A map is basically a 2D grid of stuff. A 2d grid most natural data structure is a 2d array.
The map is made of tiles. So let's make a 2d array of tiles:

class Map
{
    Tile[,] m_Tiles;  // easy and fast!
}

A tile has various properties, such as the terrain there or if the player visited this tile. These core properties are everywhere on your map, so you want them at every tile.

Your game will access the tiles by position a lot so having an array makes sense and is the most efficient solution.

Entity everywhere on the map + frequent access by position = Array of entity is good.

- Bad Array, quite Good List but not good enough
You have other entities on a map. They have a position on the map too, but all the tiles do not necessary have one of these entities and in fact most of them do not. For instance you never have an actor at each and every tile.
Since most of your map will be void of these entities it makes sense to NOT use an array. That would be a waste of memory and your saved games size will skyrocket.

class Map
{
     Actor[,] m_Actors;  // most of this will be empty! what a waste!
}

That sucks. Image the wasted memory on a large map (yeah even null pointers take memory).

Entity rare on the map = Array of entity is bad.

Ah. Well what about a List then?

class Map
{
     List<Actor> m_Actors;  // ok no waste. happy?
}


Entity rare on the map = List is good.

Hey! But I liked my array! It was so nice to access efficiently to the entity by position! Having to process the whole list of actors to see if there is an actor at a position is awfully inefficient!

Correct. That's why God created Hashtables.

- List+Hash : you are winner!

Ok we have two requierements that seem contradicting:
1 don't waste memory.
2 fast access by position.

List does 1. Array does 2.
Having 1 is nice but we REALLY wants 2, especially if you have a large number of stuff to process in your game.

Hashtables are usefull for this. You can think of them as "hollow" arrays.
- you can access them by index (called key) like an array.
- they hold only the elements you put in them like a list, they have no "holes".

When you think about it, a position (point) on the map is an index. There you have your key.

class Map
{
    List<actor> m_Actors;
    Dictionary<Point, Actor> m_ActorsByPosition;
}

Now you can retrieve actors directly by their position by querying the hashtable:

Actor GetActorAt(Point position)
{
    return m_ActorsByPosition[position];
}

(This little code doesn't handle error cases but you get the idea)
It works great. It looks and behave like an array, with very little overhead and with the benefit of no wasted memory.

We still keep the list, cause we want to be able to write things like: "for all actors in this map, do this". Getting the list of actors from the hashtable doesn't guarantee a stable order, plus you don't know what it does under the hood, it might reallocate a list each time you call it.

Think of the list as the master data structure, and the dictionary/hashtable as the slave or auxiliary data structure : you don't need it, but it proves quite usefull.

- Real life use : AI improvement
Well not quite real life but real game. I use this dual data structure a lot in Rogue Survivor, from Actors to MapObjects and Items stacks.

But I confess I was lazy once and did not use this for the Odor feature and instead kept the basic list alone.
Some actors leave odors behind them and some AIs use this to follow or chase them around.
Worked good enough, until I wanted to improve the Zombies AIs. I thought they were a bit too passive and I wanted them to more actively chase humans by smelling odors at a distance rather than just by standing around.
Implement. Test. Uh oh. With my 100+ Zombies per map performance was fugly.
I forgot about the list and used a profiler to find the problem, if there was one. I was ready to surrender the AI improvement to the god of performance :(
Well, turned out I still had the list and it was doing "find an odor at position X in a big fucking list" a lot.
I promptly repaired this injustice by implenting the companion hashtable and tadda, not only performance improved a lot, but it improved to better levels than before. In the end I had better AI with better performance at the cost of few lines of code.
So trust me, use it :)

End of post.

Shopping with Zombies

Last night Phil Stevens went shopping...
(large pic from 1680x1050 screenshot)

 ...and met some unpleasant customers. 

Basic inventory and item management done. You can grab items from the shop shelves and they stack in your inventory.

Also started to implement Food and Sleep features. You'll need to loot food in place such as shops and find proper places to sleep or you'll get bad things happen to you. I find the need for food to be an annoyance in roguelike games. But here it serves as a motivation for the player to go outside and face danger rather than just holing up in his corner, since the game is all about surviving. Need for Sleep acts like a long term stamina constraint : you can't keep waltzing around zombies and fighting undead all day, you'll have to find a place to rest. Undeads on the other hand don't have these kind of problems at all, plus considering night will have negative effects on the livings, the player will have to strategize his survival schedule.

End of post.