Coding - It's UML Time!

Sorry folks but...

IT'S UML TIME!

Note that most classes members are omitted and method signatures simplified.
They say that UML is worth over 9000 words...
...so I'll just throw random class diagrams at you.

1. Controllers

 

2. AI

NCLASS
I used NClass for this. NClass is nice for doing C# class diagrams.
http://nclass.sourceforge.net/


End of uml time.

Coding - District Map Generation

How about a coding article? It's been quite a long time, so let's have one.
Let's start with some simple.
If "recursive quad splitting" tells you something you can skip the article alltogether, as the algorithm is really only doing that. It's nothing special really.

DISTRICT MAP...
If you look at the structure of district surface maps they basically all look the same : blocks of buildings cut by straight roads. It's no coincidence, there is one algorithm that generate all the districts.

...GENERATION : Generating Blocks
How can we get  this blocky district plan?
Let's start with the whole district rectangle and nothing in it.

Mister District.

We want blocks.
How about cutting this district along two lines?

Cut

The blue lines would split the district in the middle.
That would be not very interesting for the player.
So let's deviate a bit and cut along the red lines.
We obtain 4 smaller rectangles, call them quads a, b, c, d.
a is topleft, b topright, c bottomleft and d bottomright.
Nice.
But b is a bit too small, so let's merge it with a instead.

b merges with a

Let's continue splitting shall we?
We apply the same process we did on the big district rectangle on the smaller quads (recursion).

After Cut+Merge on a,c,d.

We try to split a in 4, but the smaller quads are too small, so we merge the smaller quads and get only two quads a1 and a2. Same with c.
We find d is already too small and decide to not split it further.
We decide that's enough as there has to be an end to this madness.
From these quads we make blocks and give them numbers.

Blocks

... GENERATION : Assigning Blocks.
Looks like your average district map, with the roads and all.
Only thing, the blocks are empty.
So next for each block we decide what to do with them and fill them.

Assigned blocks

h for housing block, p for park.
Different algorithms are used to fill different block types.
Different district types will have different distribution of block types.
That's it.

THE ALGORITHM
The block generation algorithms in pseudo code (image).

MakeBlocks : Making Blocks since 1887

Start the recursion with calling MakeBlocks on the district rectangle.
Block is a class that has a rectangle property and various other content properties that are filled later.

QuadSplit is even more simple, choosing the split lines semi-randomly and doesn't split quads that would be too small ("merge"), enlarging one of the quads and marking the merged one as empty.

End of post.

Alpha 4.11 out in a day or two

Alpha 4.11 should be out tomorrow or the day after, European time.

Tested the fix, works.
Fixed some other bugs.
Added a little something.

While I was in the AI code I improved some stuff there.
...
Sounds good.
...
Of course "improved" does not mean "adding more bugs"
....
It's impossible.
....
Never happens.
....
Right?
....
Please :(

End of post.

Alpha 4.1 : Advisor hints.

A nice new feature to help clueless new players who don't know the basic controls.
I also noticed that a significant number of players seems to ignore the existance of some features (using exits, pushing objects...)

ADVISOR HINTS
You can enable an Advisor (on by default).
The Advisor will monitor your situation and provide appropriate hints.
When the Advisor has a hint available, a little annoying popup appears and prompt the player to go read the hint. You can ignore it and keep playing, but because it's kinda intrusive you'll want to read it ;)
The hints are fired from the most basic ones (eg: how to move) to more complex ones (eg: how to fire a weapon), so it won't tell you the more advanced stuff until you have read all the simpler ones.

For example, as soon as you start a new game the Advisor wants to tell you how to move:

Later on the Advisor has a suspicious fetish for items and doors:

(missing H in Shelf)

I'll add enough hints to hopefully make the basic controls and gameplay clear.
Roguelike/RS veterans can safely disable the Advisor option.

CODING
Nothing special, but it's been quite a long time I didn't show some coding stuff so let's talk about the implementation.
Thanks to the way I've done the engine (go me!) and the wonderful world of C# lambdas, it was very easy and quick to implement.
For instance, to check if it's time to trigger the "Look! You can open a door" hint I just write a line like this:
                    return map.HasAnyAdjacentInMap(pos, (pt) =>
                        {
                            DoorWindow door = map.GetMapObjectAt(pt) as DoorWindow;
                            if (door == null)
                                return false;
                            return m_Rules.IsOpenableFor(m_Player, door);
                        });
(thanks for messing the formatting, Mr Blogger)

Then I just maintain a table of hints that were already fired, to ignore those.
The Advisor state is stored in the Session object, so it is saved with the game.

End of post.

Other (abandonned) projects II

(first part here: http://roguesurvivor.blogspot.com/2010/06/other-abandonned-projects.html)
Warning : bunch of AI mumbo-jumbo ahead, you should know a bit about searching and planning. I'm too lazy right know to properly explain the algorithms and terms.

* BadBowl - an attempt at "serious" AI
For the life of me I can't get this thing running again, so no ingame screenshots, just code.
I like screens because they show I actually did work and its not vaporware :)

Idea : Solo Blood Bowl - Human vs AI.
Environement : Java, Eclipse.
Status : Abandonned.

Designing an AI for a BloodBowl clone sounded fun, so I did it. I developped the game engine and the AI at the same pace. For instance I did not implement passing yet but there was an AI you could play already against with moving, blocking, scoring, special abilities etc...
Actually there was THREE different AIs engine. 

1. SimpleAI
Engine: Selective tree search with static pruning.

Why "Simple"? Well doing a search engine with pruning sounded simple enough as I was sure I could do it since  I already did chess engines for instance. I knew it would be probably bad and slow, but at least I knew I could do it. Just curious about the results.

I knew the search space would be insanely large so I did pruning at each level of the tree. In other words selective search with static pruning. As usual with these kind of approach, the idea being that "good" moves should get more attention than "bad" moves. It sounds much less risky than in chess for instance, because you are searching only your own moves, not the opponent, so less tactical blunders caused by ignoring some move lines.

I don't remember the details (how did I handle turnovers in the search, risk taking with probabilities etc..).
Here's the actual main search method code in Eclipse, arranged into one messy large picture:

As you can see its just a standard search with hashing and prunning.
The resulting AI was mediocre at best and the AI thinking was way too slow.
As usual with tree searches, it was hard to determine what was the weak point causing bad choices : the evaluation function? the search/pruning?...
So I did number 2...

2. BeamAI
Engine : Beam search of plans.

Instead of searching a tree, this AI maintains a list of plans and try to improve them. I read about it in some AI papers, mostly about a Diplomacy AI engine by a French guy, and it sounded great.
In this context, a Plan is a list of successive AI moves. Improving a plan means adding a move that makes the terminal position better. The plans are initially seeded with all or a selection of legal moves.
Sounded great, easy enough to do and easily debuggable since I could for instance print all the plans at all times to monitor the AI decision process.
I had the brilliant idea to write the algorithm in the comments of the code, much better than random code screens, so here it is with a bit of code :

It worked quite well, producing occasional flash of semi-brilliance and actual planning, but was very bad at handling risk taking (either too safe or too insane) and tended to gravitate around a main line (with only superficial changes like one square move difference), ignoring alternatives (poor space exploration, exploitation vs exploration dilemna as usual).
As usual, how to balance the search vs the evaluation... Annoying. Nice actual AI but annoying. Really.
I was fed up with search methods and the lack of control, so I did number 3...

3. RulesAI
Engine : Rules from a Rule Book.

Rules. They are simple, easily controllable.. but predictible and about as un-AI as you can get. But what the heck, it actually works.

1. Each pawn is an Agent. An Agent has a Rule Book. A Rule Book is a set of ordered Rules, from the most urgent/interesting one to the least important.
2. When the AI wants to play, it ask all its Agents what they want to do and the winner (the Agent firing the highest rated rule) does its action.
3. When asked to, the Agent checks its rule book, line by line, until a rule gets fired, and return the resulting action.

Very simple and you can tune a lot of things (for instance a "strategic focus" to arbitrary reward some agent or some kind of rule). If you order and design the rules correctly it produce surprisingly decent AI for a quite low CPU cost when compared to search methods.
Example  of a Rule Book with actual rules :

Individual Agent actions made sense, problem was coordinating the different agents... For instance when attacking I could easily outflank it like you would do against a novice player (move the ball to the center, fix the opponent there, then escape/pass to the wings).
So decent tactics (it did tackling and support very well) but mediocre strategy, which is kinda a classic for strategic games AIs...

* Ok but uh what about Rogue Survivor?
Rogue Survivor AI = KISS : Keep It Simple Stupid.
Its similar to RulesAI presented here, but with much more stuff "hardcoded" and no real engine behind it.
It kinda works because agents are not supposed to cooperate a lot and just do their own stuff.
I did a post about it.

Since you were brave enough to read all this crap, here's a super secret RS screenshot for you :

(that part of 4.0 is not completed yet)

End of post.

FAQ FIX FUK FAR

FAQ
I started writing a Game FAQ page. The link is right above, under the banner.
Read it, it could save your life, make you win the lottery and find a (better) girlfriend!

FIX
I tried 5 different fixes for the minimap bug.
Not a single one did anything.
I now officialy hate Intel graphics cards, managed directx, black textures, graphic streams, byte buffers, lock flags, pool flags and usage flags.
I guess I'll have to write a shader just for rendering the minimap.
But that would work only on some Intel cards that have pixel shaders.

http://www.intel.com/support/graphics/sb/cs-014257.htm 

I'll start working on that later.
I'll do all the gameplay stuff for the next version then look at this problem again.

Special thanks to Andrew R and austin richardson for testing the super secret fixes!

FUK...
...The installer.
Yes ClickOnce from Microsoft I'm looking at you. I'll use a simple zip next time thank you.
I'll add something in the FAQ to manually remove the game. But be prepared to remove files into some stupid folder you probably never heard of (a super secret cache) and edit your registry. Lots of fun.
Sigh.

FAR
Well not quite. But 3.1 progressing.

End of post.

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.

Fun with alphas!

I'm having great fun with my alphas versions! I mean in trying to fix compatibility bugs...
It's not as bad as it sounds. Its part of the job fixing silly stuff. That's why game companies have beta testers and a bunch of different machines to test on. Coding problems I can test most of them by myself but hardware I can't. So I can only rely on brave volunteers feedback.
Some stuff I learned: 

Deploying .NET 32 bits to 64 bits
Bug: You compile and run on 32 bits machine but it crashes on 64 bits.
Solution: In VS use the the Configuration Manager and compile for "x86" platform, not "any cpu".
To enable the Configuration Manager you must enable advanced options.

Distribution with ClickOnce
Thats what "publish" in VS does. It will download the right dlls for the user.
The bad thing is that it hides the application in a silly cache directory and only adds a mysterious im-not-quite-your-usual-link to the executable and nothing else.
Since I want some files to be available to the user (game manual and post mortem files) I'll have to find a way to copy these files somewhere else. Most likely the desktop or some C:\folder. But then ClickOnce uninstall won't clear those files and I'll have to mess with something. Bah.
I hate applications that leave crap after uninstall so I'll have to do it cleanly. I hope I won't have to write a ClickOnce deployement class or something. Talk about making it simple.

Creating DirectX textures
Bug: crash when creating a new texture on some gfx cards.
I was impressed by how Managed DirectX is easy to use. In my memories DirectX was something awfully verbose and convoluted with lots of LPDDIRECTSOMETHING crap and tons of lines of code just to fucking init a device. That was from DX6 or DX7 days in C/C++. Its so much simpler now, even more in .NET.
Good. But I was bit a naive in thinking I shouldn't have to check gfx cards capabilities and limitations when creating textures. So if I pass a parameter value that offends the gfx card, DX throws an error at you with little explanation. You have to guess what parameter is the culprit. So you have to annoy the people who tried your game and crashed with request about trying each one of your code fix. Thankfully they seem cooperative and glad I'm trying to fix the game.
Solution? : In Texture ctor the culprit is either numLevels and/or  texture size not a power of 2.
Wth? I thought texture sizes ^2 was a thing of the past.
I hope there is set of texture constructor parameters that fits for all gfx cards but I'm not too sure now...

End of rant.

Rogue Survivor Design approach

(You should know about OOP and the design issues behind designing a roguelike game to read this article)

 OOP for Roguelikes
 When designing a game architecture with an OOP (Object Oriented Programming) approach, one naturaly tend to put the data and the logic associated with a game entity in the same place, namely a class.
So you create classes like Item, Actor, Map and the likes and make a one-to-one relation between a game entity and an instance of a class (object). 
One particular Sword entity in the game will likely be an instance of ItemMeleeWeapon, which a hiearchy like ItemMeleeWeapon is ItemWeapon is Item.

Entities Interactions : Assigning responsabilities
Works fine. But then what about entities interaction? Say the player actor wants to open the big door.
Who does it? There are many differents ways and paths to choose. The most common are:

1. The Actor does it: playerActor.OpenDoor(theBigDoor), which in turns calls theBigDoor.SetState(OPEN) etc...
2. The Map does it: map.ActorOpenDoor(thePlayer, theBigDoor)...
3. The Action does it: openDoorAction.Execute()...

Thats works fine too. But to be consistent in your design you have to garantee all actions will follow the same path and logic, otherwise you will end up with anarchic code.

Shared responsabilities = Spaghetti Logic = Bugs and Refactoring Hell
The danger -read: the source of bugs or game logic inconsistencies- resides when one entity (active) initiate an action on another entity (passive) which could trigger a response somewhere else (eg: the door electrocutes the actor) which in turn could trigger another response (eg: the actor roll for electrocution resistance) etc.. and you end up with spaghetti logic. In general this ends up provoking bugs, because somewhere in one of your derived classes you made an assumption about the caller or some property that is broken by the logic chain triggered by the action initiator...
People who take this standard OOP approach tend to search for the "perfect" architecture, refactor their code a lot and most of the time aim for a roguelike engine rather than a game. It works but with great pain.

Game Data separated from Game Logic : Multiple Data, One Controller
In Rogue Survivor I choose since the start to go with a Data-Driven approach with a single Controller.
All the game entities are represented by Data classes. Data classes are "stupid" and only know to maintain themselves. Data classes use inheritance only when requiring additional fields and properties. Eg: ItemWeapon derives from Item because it needs additionnal data to represent a weapon.

All the game logic in centralized in one place, the Game. The RogueGame class has absolute control on everything, is the game master and holds all the game logic.

Actions are Data too, whose job is only to call the RogueGame appropriate methods when checking for legality or executing. Remember, as Data classes they have no game logic in them at all. They are like a dumbed down version of the Command design pattern.

Types of entities (eg: the skeleton actor type, the crowbar item type) are instances of Data classes too, called Models (eg: skeleton actor type is an instance of ActorModel).

AIs are special cases because I consider them as abstract game logic, since the AI logic in itself does nothing in the game world, it just computes stuff and produce an Action command.

The Holy Grail?
Certainly not. In other pet game projects I favor other architectures such as the standard OOP mentionned above.
For Rogue Survivor it just works and is very easy to maintain. All architectures have limitations and flaws, you just have to accept them.

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.