search

google-code-export / evennia

Automatically exported from code.google.com/p/evennia
Other
1 stars 0 forks source link

Feature suggestion: Contrib: Grid Quad tree #203

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago 
A) Describe the suggested feature and how it is supposed to work and behave
to the end user (player or admin/coder).

A Quad tree (http://en.wikipedia.org/wiki/Quadtree) could be an efficient 
contribuion for handling room grids (i.e. muds wanting to use NESW directions 
on a fixed grid rather than more abstract spatial relationships). This would be 
an optional Contrib, since not all games have use for a grid like this.

B) List briefly your arguments for why you think this new feature should be
included in Evennia.

1. The advantage of a Qtree is that it's efficient to find adjacent locations, 
and also nested locations or zones (all rooms on the same branch). This means 
one could use the Qtree for quick determination of distances between rooms, 
path-finding algorithms and so on. Exits and so on would still work the same, 
but one could use the Qtree as a global map of the game grid for fast 
relational lookups.
2. One could envision a octotree as well to represent full 3D coordinates 
(height as well), but that lacks many advantages of a Qtree; probably the 2D 
version will be more commonly useful. 

C) If you have any suggestions on the best way to implement this new
feature, write those ideas below.

The Qtree itself would need to be a separate module with a global object stored 
in the database (e.g. as a dictionary using ServerConf model). What is stored 
is only dbrefs, not actual objects. The module would need to establish access 
methods for manipulating the tree. Common commands such as @tunnel and @delete 
would need to be made aware of the Qtree so as to update the spatial 
information. So custom commands would need to be added to Contrib as well. 

Adding this as an idea so I don't forget, it's not clear how useful this would 
be in practice or how easy to implement.

Original issue reported on code.google.com by griatch on 6 Dec 2011 at 9:43

GoogleCodeExporter commented 9 years ago

Original comment by griatch on 6 Dec 2011 at 9:44

GoogleCodeExporter commented 9 years ago 
Looking more into it, for the use of a 2D gaming grid, an 
[http://en.wikipedia.org/wiki/R-tree R-tree] is probably more appropriate. 
There are also efficient python implementations of this available already. 
.
Griatch

Original comment by griatch on 7 Dec 2011 at 2:12