More library goodness
http://www.byond.com/developer/Theodis/Region
Like it says in the description it's pretty much a wrapper on the flood fill algorithm. It works similar to my RegionMap library except that it only gets an individual region rather than divide up a set area into many regions. Another difference is that it isn't bound to a turf grid like RegionMap so Regions can be built out of any graph style data structure as long as you can provide the node connections from a node as well as having a starting node you can build a region from it.
However RegionMap is significantly faster per region over a large area so if you want to divide up an entire map it is a better solution if it is possible(ie your map is built out of turfs rather than say datums for a text game or something). Not to say Region is slow just not as fast. On my computer a region built over a 10,000 tile area took about 2 and a half seconds. And on smaller areas like in the demo of about 200 tiles it on average takes about 5 milliseconds per call so on room sized areas of under 20 tiles you should be able to call it without noticeable overhead hundreds of times in a tick.
To try and speed up the Region library I built a special list data structure to handle the contents list. The reason why Region is slower than RegionMap is because Region stores all the nodes its been to in a list whereas for RegionMap it's just flagged on a 2D list that matches the size of the search area. Whenever a new node is being added the algorithm needs to check if it's already been added. With Region it needs to search through the whole list to check if the node is already in so as the list gets larger and larger this check gets slower and slower. With RegionMap it just indexes to the grid position which is just as fast regardless of how big of an area it's already added.
On a normal unsorted list you need to check every item up to the item you are finding it to find it. However if the list is sorted you can perform a binary search which requires significantly less checks which is why my special list should have been faster. Unfortunately that didn't work out because while it doesn't take as many checks each check is much slower for my list because the built in find has direct access to an objects unique hash whereas I need to use \ref to build a string version of it for each check for both datums being compare.
But I've made the list available for anyone who is curious about it.
http://www.byond.com/developer/Theodis/RefSortedList
If we ever get a more direct way of getting at an objects hash value it may actually be more useful. At the moment it's probably only useful for quickly taking out duplicate values and nulls in a list.
This is only useful if the item order isn't important as it will sort out everything based on it's \ref value.
Like it says in the description it's pretty much a wrapper on the flood fill algorithm. It works similar to my RegionMap library except that it only gets an individual region rather than divide up a set area into many regions. Another difference is that it isn't bound to a turf grid like RegionMap so Regions can be built out of any graph style data structure as long as you can provide the node connections from a node as well as having a starting node you can build a region from it.
However RegionMap is significantly faster per region over a large area so if you want to divide up an entire map it is a better solution if it is possible(ie your map is built out of turfs rather than say datums for a text game or something). Not to say Region is slow just not as fast. On my computer a region built over a 10,000 tile area took about 2 and a half seconds. And on smaller areas like in the demo of about 200 tiles it on average takes about 5 milliseconds per call so on room sized areas of under 20 tiles you should be able to call it without noticeable overhead hundreds of times in a tick.
To try and speed up the Region library I built a special list data structure to handle the contents list. The reason why Region is slower than RegionMap is because Region stores all the nodes its been to in a list whereas for RegionMap it's just flagged on a 2D list that matches the size of the search area. Whenever a new node is being added the algorithm needs to check if it's already been added. With Region it needs to search through the whole list to check if the node is already in so as the list gets larger and larger this check gets slower and slower. With RegionMap it just indexes to the grid position which is just as fast regardless of how big of an area it's already added.
On a normal unsorted list you need to check every item up to the item you are finding it to find it. However if the list is sorted you can perform a binary search which requires significantly less checks which is why my special list should have been faster. Unfortunately that didn't work out because while it doesn't take as many checks each check is much slower for my list because the built in find has direct access to an objects unique hash whereas I need to use \ref to build a string version of it for each check for both datums being compare.
But I've made the list available for anyone who is curious about it.
http://www.byond.com/developer/Theodis/RefSortedList
If we ever get a more direct way of getting at an objects hash value it may actually be more useful. At the moment it's probably only useful for quickly taking out duplicate values and nulls in a list.
var/RefSortedList/r = new(somelist) r.RemoveDuplicatesExact() somelist = r.contents if(somelist[1] == null) somelist.Cut(1,2) |
This is only useful if the item order isn't important as it will sort out everything based on it's \ref value.
Posted by Theodis on Wednesday, January 21, 2009 01:27PM
- 1 comment
(link)
/
#2 Theodis:
Ahh neat just barely noticed this box here! Anyway yeah I could package it up as a library. But I think a stack works more efficiently when implemented with a normal list rather than a linked one.
Sunday, June 07, 2009 09:09AM
#1 IainPeregrine:
Ahoy Theodis. I use a linked list structure you posted on the forums ages ago (ID:347289). I've even edited my BYOND directory so that it shows up as a library (Theodis.Queue). Perhaps you could release it as such, so that others can use it, too? You can find it, in the form I use it, here.
I took the liberty of adding a Stack() proc so that the same linked list object can be used for both stacking and queuing. Thanks.
Thursday, June 04, 2009 03:03AM