ToME: the Tales of Maj'Eyal

Everything about ToME
It is currently Tue Nov 13, 2018 7:01 pm

All times are UTC




Post new topic Reply to topic  [ 6 posts ] 
Author Message
PostPosted: Wed Dec 02, 2009 1:17 pm 
Offline
Master of Eyal

Joined: Wed Jul 24, 2002 9:26 pm
Posts: 10230
Location: Angolwen
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

_________________
[tome] joylove: You can't just release an expansion like one would release a Kraken XD
--
[tome] phantomfrettchen: your ability not to tease anyone is simply stunning ;)


Top
 Profile  
 
PostPosted: Wed Dec 02, 2009 4:52 pm 
Offline
Sher'Tul

Joined: Mon Jul 07, 2003 5:22 pm
Posts: 1461
Location: Finland
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.

_________________
Zothiqband -- still an Angband variant.


Top
 Profile  
 
PostPosted: Wed Dec 02, 2009 6:43 pm 
Offline
Spiderkin

Joined: Sat Mar 18, 2006 12:48 pm
Posts: 482
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


Top
 Profile  
 
PostPosted: Wed Dec 02, 2009 7:10 pm 
Offline
Master of Eyal

Joined: Wed Jul 24, 2002 9:26 pm
Posts: 10230
Location: Angolwen
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

_________________
[tome] joylove: You can't just release an expansion like one would release a Kraken XD
--
[tome] phantomfrettchen: your ability not to tease anyone is simply stunning ;)


Top
 Profile  
 
PostPosted: Wed Dec 02, 2009 8:54 pm 
Offline
Sher'Tul

Joined: Mon Jul 07, 2003 5:22 pm
Posts: 1461
Location: Finland
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.

_________________
Zothiqband -- still an Angband variant.


Top
 Profile  
 
PostPosted: Wed Dec 02, 2009 9:11 pm 
Offline
Master of Eyal

Joined: Wed Jul 24, 2002 9:26 pm
Posts: 10230
Location: Angolwen
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 ...

_________________
[tome] joylove: You can't just release an expansion like one would release a Kraken XD
--
[tome] phantomfrettchen: your ability not to tease anyone is simply stunning ;)


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group