How much "many monsters" is many monsters?

[darkgod]

AKA what do you consider a very big number of monsters per levels ?

I'm fighting with the AI code to not run slower than a sleeping snail but I just cant seem to get it right.
The slow part is target aquisition, each monster parsing each monsters to find their target is kinda hellishly slow

[Nerdanel]

I'd say a few hundred monsters on a level is a lot.

Any chance you could do the code in C? Lua is fast for a script language but it's still a script language. Though, if there is a big asymptotic performance difference from the old ToME code, chances are the algorithm is at fault and writing it in C wouldn't fix the problem, only mitigate it a little.

So if n monsters are each checking n monsters, that should be an O(n^2) algorithm unless you find some trick to make it faster. If the algorithm's asymptotically slower than that then there's something seriously wrong. Even if it is O(n^2) and still much too slow, one thing that comes to mind is that monsters don't need to check every monster in the dungeon, just the ones they are aware of. If there can be at most m other monsters on the m squares to be checked near any one monster, the algorithm becomes O(n) with a large constant multiplier. In that case having tons and tons of monsters total on a level won't degrade the overall performance so dramatically.

[AnonymousHero]

Warning: Bad ideas may be ahead! Caveat lector!

A pretty reasonable technique would be to have a max awareness distance and first culling your list with a simple "in-rectangle" test (x,y) \in ((x-r),(y-r)),(x+r),(y+r)) before doing any kind of distance comparison. This is still O(n^2), but probably with a lower constant.

If you need better complexity you could maintain a quad-tree (think 2D equivalent of http://en.wikipedia.org/wiki/Octtree ) containing all the monsters/objects of interest and updating it whenever a monster moves. Since level size is fixed once a level is created you could also get away with a fixed-depth quad-tree. Then you'd only have to check the monsters/objects in rectangles adjacent to the rectangle of the object you're considering. This would give you O(n*m) where m is usually a lot smaller than n (obviously depending on general monster density).

A third option: Have each monster/object maintain a list of references to all other monsters, ordered by distance. Whenever a monster/object moves you can update this list appropriately. The update could use some sort of bubblesort-esque way to update the lists efficiently.

EDIT: Eh, there's actually a quadtree article at WP: http://en.wikipedia.org/wiki/Quadtree

[darkgod]

I believed at first it was lua's fault, but yes it is the fastest VM around and anyway T3 was doing much the same anyway...

I'm experimenting with a coroutine(think of it like a cooperative thread: a pausable/resumable function) that permanently comptues the distance to all actors for all actors and taht does itin small steps which are called every time the engine has nothing better to do.

It does improve performence tenfolds, but it is still bad. I believe some algo must be wrong too somewhere.

Maybe a better version would indeed be to insert into a "to process" list each actor that moves and then in that idle coroutine process them.

(My tests are with 400 monsters which is already a lot)

I have an idea to do it with some C thrown inside but I cannot fathom how it could make it that much faster, there must be something else

[Nerdanel]

Some further obvious ideas:

- If a monster is sleeping, don't bother acquiring a target for it.

- If a monster already has a target, check if it's still valid. If yes, don't do anything.

- Don't check for targets every tick. Check only when a monster has enough energy to take an action and only for that monster.

[darkgod]

I'm doing all that, except sleeping monsters. Not implemented yet.
I'm not sur how to "unsleep" monsters ..
I dont want to tie it to the player, as I'm really trying to make the player non-special.
I will if I really need to but ...