clintbellanger/flare-engine — pull request #299 by stefanbeller (2012-12-21 19:41:54+00:00)
Title: Rewrite enemy group spawning.

The algorithm up to now worked like this:
foreach enemy group:
* create a list of valid locations.
* pick a random number N to determine the number of enemies placed.
Do N times:
* pick a random index from the valid locations list.
* place enemy there, update valid locations list.

The above algorithm made sure that once N was picked, the exact number
of enemies were placed, unless there was absolutely no further valid
location. However setting up a list of valid locations is a big deal.
(Consider frontier_plains for example. There are some enemy groups all
over the map, having a width*heights=50*100=~5000 entries in the valid
locations list.)

The new approach looks like this:
foreach enemy group:
* pick a random number N to determine the number of enemies placed.
* pick an upper bound M on failed placement attempts
Try N times (and upper bound of failures not reached):
* pick a random location from the enemy group area to place enemy
* either decrease N or M depending on success

The new presented algorithm doesn't require huge data structures
(low memory overhead on map loading) and is also faster (no init/maintenance
of said data structures)
However there is a theoretical possibility to have less enemies placed
than initially determined (N). As N is a random number,
the player will not notice. Also by having 3 tries on average per placement
of an enemy this only impacts when the enemy group area is nearly
unwalkable.

About performance:
This change improves map loading times.

1) I setup a debugging warp, which warps the player to the warp position
itself, so the player is stuck in an endless warping. The whole warp
cycle was measured and printed to stdout. This scenario is best as nearly
all resources are cached by the engine, so the algorithms draw the cpu time.
Frontier plains before ~ 400ms, after ~250ms

2) setup a warping cycle with 2 maps (frontier plains to frontier outpost
and back again). This removes some cache effects.

whole cycle (2 warps) before ~730 ms, after ~520 ms