Speed optimizations?

[smogo]

This sounds interesting.

The math is simple and the bounding areas/volumes can be precomputed and stored in the db since mobs always spawn in the same location AFAIK.

This is true as regards to standing mobs. Those that move are a bit different.
Generally speaking, this is a kind of BSP you refer to, clipped by Aggro/Assist/whatever radius. Such BSP exist in the client's zone files. It seems also that the map package in zone (will|might|could|ought to) be used to describe, and thus maybe partition, space. It uses *.map files, but i spent very little time looking at what it does, so maybe it's just missaying.

BTW, i found something about caching : you must keep it up to date . I came accross the idea of tracing despawns, and, yes, after despawn, using the reference from the cache doesnt end up too well ... Still some work on that topic.

[Eglin]

Originally Posted by smogo

This is true as regards to standing mobs. Those that move are a bit different.

Aye, but I'd venture a guess that for those to whom los is a consideration (indoor critters), their natural mobility is restricted to an area no larger than their intended los. Thus, it doesn't matter.

Generally speaking, this is a kind of BSP you refer to, clipped by Aggro/Assist/whatever radius.

Generally speaking, I'm referring to bounding volumes. BSPs are a way of partitioning space. Bounding volumes are a way of approximating an object's geometry - in this case the object is the mob's line-of-sight. The biggest difference between the two can be seen as the area around the bounding volume grows. My scheme doesn't care - a point is either in the box or out of it. BSPs, on the other hand, get very very ugly in such a case (which is why doom is an inside-only game).

Such BSP exist in the client's zone files. It seems also that the map package in zone (will|might|could|ought to) be used to describe, and thus maybe partition, space. It uses *.map files, but i spent very little time looking at what it does, so maybe it's just missaying.

Whatever the case, I think that utilizing some geometry is going to prove a better solution for checking los than the existing baby-steps method. I'm definitely NOT going to write a bsp tree implementation, though. Espescially when perfectly satisfactory results can be had by simply specifying aggro area w/ a rectangle instead of a radius.

[Eglin]

Originally Posted by smogo

here is a piece of code that might help.
<snip>
the other code (Terrain and Hashtable and Vector ... )are a available here
http://perso.wanadoo.fr/afou/khalzed...ighbors.tar.gz
<snip>

I hope you don't take offense at my posting the following comment, since it is clear that your heart is in the right place.

I just downloaded and examined some of your code and it is the funniest thing I've seen in a while. The "hashtable" in particular is the funniest data structure I've ever seen.

You state in the code that it should have O(n) inserts and O(log n) searches. This is the first clue that something is seriously wrong. A proper hash table should have O(1) inserts, O(1) deletes and O(1) lookups (assuming good hash functions). What you have is really a sorted vector. The really funny part, though, is when you realize that it isn't even a good sorted vector! The search function is recursive, which is a little ugly. The really funny part is that you walk the vector to insert in sorted order instead of using the binary search function you've already created. And all of these numbers are biased by using comparisons as our atomic operation. If you look at overall efficiency, the story saddens considerably more.

A good knowledge of data structures is the most dramatic difference between a good programmer and a poor one. In my experience, 80% of all programming tasks are solved by setting up appropriate data structures and then manipulating them (classes are data structures when using this view). I commend you for trying to write your own, since that can be an excellent way to learn, but still felt compelled to rip on you a bit for such a funny implementation.

[smogo]

i wont take offense. Still, it saves over half cpu....

The structures where built from scratch, and what is called a hashable, well, it's a keyed set. Think of searching a 'flat" balanced binary tree. Whatever the names or code involved, setting up data structures was a waste of time in my mind at that time.

i would encourage anyone willing to provide new structures to the project

It could event have used linked lists, as this -crappy- piece of code's efficiency comes not from data structures. Well, good and efficient DS would help.