For some time I want to start writing series of articles about various aspects of game development, and as always, the first step is the hardest one. I never found enough time to start, as game development takes priority in the first place over other game related activities. But as I said first step is hard one.

During the development of the current version, I got to the point where more complicated modules need to be implemented (or old ones refactored), which I saved for the end of the development cycle. One of these modules are different "maps", which this article is all about. We are not talking about visible map you can see on the screen but rather about those invisible ones, that helps game logic in various ways. The game itself uses a large number of these maps, and let me name some of them:

• approach map
• flee map
• wander maps
• fieldof view
• static and dynamic lightmaps
• perception map
• and few more that are not so important to mention

Approach, flee and wander maps are used for enemy movement, field of view to get information who is in the sight of player, and lightmaps to draw illuminated parts of the dungeon.
Development has been started only with approach, flee and wander maps, but as you see I have a tendency of increasing number of these maps as developing process evolves, which is normal. Needless to say, the greater was their number, the slower was the game.
Fortunately not all of them are updated during every iteration of the game. For example, wander maps are created once the level is entered, and recreated only if some major event occurred that changed look of the level.

Approach and flee map are a bit different, they are created always on the end of rogue's movement, and flee map is partially based on approach map also. And these maps are based on one function: Flood Fill algorithm which mimics Chebyshev distance algorithm. As distance increases from x,y point, the weight increases also.
The function was quickly and dirty written and unfortunately it remained in code up to the current version.
It works on the following principles:

• Fill map with some big number
• Make start point with value 0
• Flood Fill

    function FloodFill(int x, int y) {

     # for every tile around x, y

     # check if around tile is passable and its weight is greater than ours

     # set its weight as current weight + 1

     # and call floodfill recursively with (xnext, ynext)

    }

As you can see, nothing special. Function is short and simple, but with one major drawback. Slowness. On a normal level it had for about 28K recursive calls. With a little optimisation and a few rows a code, the number of calls has been reduced to around 9K for a 64x40 map, which was quite acceptable. And because approach and flee map creation is done once every movement tick the optimization wasn't the priority task.

(DevNote: Approaching of the monsters is solved very simply: monsters moved downward the map taking route which had smaller weight up to the point when AI took decision mechanism.)

During the development of one demonic monster, I got to the point when I needed to develop one of their vulnerabilities, that is, they can be bound. Bound demons become companions of the player and attack other monsters.

Let me explain how binding works. At a moment monster get bound to the player, he gets friendly with player and unfriendly with other monsters. If monster was targeting player at the moment of binding, he gets peaceful with player, and on the next turn he check if there is any player's enemy in vicinity. If there was on enemy, he targeted it, approached and attacked, and if there were several ones, monster could act in several ways, but mostly he targeted closest entity, approached and attack it. It worked flawlessly, and it had one big problem.

You can ask, what can be the problem with this implementation? It sounds good!
The problem was the fact that every entity in the game, every monster and players now have its own FOV, approach and flee map. Until now monsters used players approach map, and they didn't approached each other. All this led to that above mentioned floodfill function threw engine to its knees. It was time for a change. After some research instead floodfill, Dijkstra's algorithm is chosen and implemented. Current unoptimized implementation accelerated map creation up to 400%!

For testing purposes I made 2 groups of enemies with 10 members each. Groups contained fighters, healers and wizards, which attacked each other. It was a real battle with healers healing warriors in close battle with other team's warriors, while mages were casting fireballs.

It was a very exciting sight!

P.S: Yeah, new version will bring also packs, which acts and fights as a group.