Elemental Beta has started!
Posted by Theodis on Friday, September 18, 2009 01:58PM
- 3 comments
(link)
/
Members say:
yea +2,
nay -0
Working on another map tool
Kuraudo brought up how annoying data entry is in a forum post(
http://www.byond.com/developer/forum/?id=710218) which is quite silly especially for fan material since all the data is already out there and it's a lot faster to simply write a tool to convert the data available into the format you need. Not exactly what he was whining about but gave me some interest in fiddling with making another tool for converting an image of a game map into a BYOND map and to chop up a tileset from it as well.
Took me 4-5 hours of programming work but I finished my tool and tested with the FF1 maps at
http://achurch.org/ff1-maps.html . And generated
http://www.byond.com/developer/Theodis/FinalFantasy1Maps .
All that's left to do is some code clean up and to set up a UI for it. At the moment it's just hard coded calls the the programs functionality.
Feel free to use the demo project for whatever, but remember that the map data itself and graphics are property of Square so if you face any legal problems with it it'll be Square after you not me. People that write fan games don't seem to be too concerned with that so have fun with it :P!
Posted by Theodis on Sunday, July 26, 2009 01:34PM
- 1 comment
(link)
/
Members say:
yea +2,
nay -1
Complex pathfinding
My pathfinder library is very robust, powerful, and I get the feeling is underused compared to what it is capable of. To demonstrate the power of the library I whipped up a demo to show how the library could be used for non standard movement.
The limitations on movement in the demo are as follows
Mob can move forward or backward
Mob can only turn by 45 degrees when also making a move in that direction
Mob can't clip corners when moving diagonal
Originally I was going to use a tank graphic but then I remembered I can't draw and just went with an arrow instead. Just click on the map to move to that tile.
http://www.byond.com/developer/Theodis/ ComplexPathfindingDemo
And if you cut out the comments the amount of code to make that work is actually pretty small for quite an impressive effect.
This library has many potential applications and the demo provided with the library just shows the basics of how to use it. Since I haven't really used it myself I don't have too many ideas for practical applications in BYOND that people might need it for. So I'm open to suggestions for demo ideas if people are having specific pathfinding issues they need an example of a solution for.
[Edit] And if you want to have more fun with you can easily control the possible movement since I did it on a case by case basis in the AdjacentNodes proc. If you want to see it pathfind without moving straight forward just comment out the line that tests and adds nodes for forward. Or if you want to disable turning while moving backwards, or just left turns it's real easy to do with the code and interesting to see how it comes up with paths without certain kinds of movement.
Posted by Theodis on Sunday, February 08, 2009 08:45PM
- 9 comments
(link)
/
Members say:
yea +3,
nay -1
(Edited on Sunday, February 08, 2009 08:55PM)
Updated Region
A post by LummoxJR made me realize that something similar to what I was attempting with my RefSortedList is already hard coded into BYOND with associative lists. I updated my Region library to use them rather than standard lists and got a massive performance boost which should make it run much much better on large areas and even a good performance boost on smaller ones.
http://www.byond.com/developer/Theodis/Region
Posted by Theodis on Wednesday, January 28, 2009 07:17PM
- 1 comment
(link)
/
Members say:
yea +4,
nay -1
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.
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)
/
Members say:
yea +2,
nay -1
#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