There hasn't been many AlphaMapper updates lately. You're probably thinking, "Well, it must be dead, for real this time!"
You're wrong. In the most imperative sense of the word. I've just been really busy the past few months. I have been dealing with medical issues (was recently diagnosed with Type II Diabetes) and have been busy with a project at work.
Things are once more beginning to normalize and as always... my eye is back on AlphaMapper. I actually had started some work about two weeks back, but ran into a problem. The database of the property in AlphaWorld is BIG. I mean really big. There's a lot of objects in there, and I only have a copy from around the middle of last year. I went to perform some updates on this database and hit a snag: Neither my server, nor my PC have the sort of RAM needed to operate on a database of that size.
So what's the solution? I bought new server parts and I am rebuilding my server later this week to better support the AlphaMapper database.
Now, with that... I must admit, I won't be resuming work on AlphaMapper itself soon as that is done. There's some peripheral projects, related to the data from the AlphaMapper database, that I would like to build up and release to the community. They're relatively small, easy projects that should be easy to implement. Projects that should definitely benefit the AW community as a whole.
Once those are out of the way, I'll be digging back into AlphaMapper proper. Finishing up the action command parser that I had started back in December, and then getting all of this put together into the final product: An application capable of generating maps of AlphaWorld.
There's still some areas I'd love to revisit and improve, but I believe in the interest of getting maps out sooner, rather than later, I'll visit those in future versions of the project.
Tuesday, February 21, 2012
Thursday, November 17, 2011
Building in Clusters
While I work on finishing up the final bits of AlphaMapper in terms of rendering maps, I have been also working on some side project ideas of what to do with all of this property data and how to link it to the AlphaMapper interface.
We all know and love AlphaWorld Property Search, which is a sister project to AlphaMapper that is built and maintained by my good friend Ima Genius. It has been a useful tool in helping people recover lost property. There is one minor pitfall to it, though. People tend to build... a lot. Some people have built upwards of nine million objects in AlphaWorld. That's a crazy huge number. If you've even built a few thousand objects, sorting through the list of objects can be quite time consuming and daunting, trying to find that one object that belongs to some long-lost build you built some time in the past.
Over time I've kept thinking that there must be a solution. There must be a way to group these objects into things that are likely to be distinct builds by you, so that you can just look at the groupings and go visit each one, instead of trying to filter through a list of objects. I started researching and learning. I finally came across what I believe to be the answer: Cluster Analysis.
Cluster analysis is where you take several points in space and using one of the many different cluster analysis algorithms you classify them by some potential logical grouping. This sounds exactly like what I want to do for AlphaMapper.
Last night I took some time off from the main AlphaMapper code to prototype a cluster analysis algorithm. Using some randomly generated cluster data, I was able to identify clusters with ease. The particular algorithm I picked has some short comings, but there's a better version of this algorithm that I plan to implement for AlphaMapper.
As you can see in the image above, clusters that should logically be considered contiguous are some times being split into two separate clusters. These clusters tend to be overlapping clusters with odd shapes and densities that don't quite match the other clusters. This is something I plan to fix for the eventual introduction of this feature in AlphaMapper; however it is something that can most likely never be completely fixed due to the nature of the data and this class of algorithms.
So, now that I've identified clusters, what can I do with them? The idea is to take the set of points for each unique cluster and run it through another type algorithm called convex hull which is a way of taking a set of points and finding a convex polygon that best fits around the given set of points. I can then take the polygons output by this algorithm and store their points in a database and relate all of the objects contained inside of them to the polygons.
This is where the fun begins. Having this location data and polygon shapes a user can go to AlphaMapper and display these polygons on the map to indicate places that are most likely to be distinct builds that they've made in the past. They will overlay the map much like the roads do on Google Maps. This way you can see how they relate to the objects under them.
Another cool thing that I can then do, is that since I've related these polygons to the objects that are contained within them, I can make it so that you could search for specific object types, descriptions, actions, etc and get back only those likely builds that contain those specific types of objects.
Another nice thing about the algorithm I am using, is that it can also get a list of those points (objects) that don't belong to any specific cluster (build) and store them. So this way a user could also find all objects that they've built that aren't a part of any specific build. This can help them locate lost seed objects and such.
There's a lot of potential in this system and this is merely the tip of the iceberg for the things that I am capable of getting from all of the objects found in AlphaWorld. There are certainly other useful things I may be able to extract from the data to help users of AlphaMapper better use the mapper and interact with it in ways that weren't previously possible with either the old AlphaMapper or AWPS alone.
I'd also like to make a privacy note. Many builders are concerned that others will be able to find their secret builds. This will not be the case with AlphaMapper and what was discussed in this article. Only you (or anyone you give permission to) will be able to view your own property and builds mashed up against the maps. There may be certain exceptions to this rule for historical reasons (i.e. citizens who no longer use AW or have passed away).
We all know and love AlphaWorld Property Search, which is a sister project to AlphaMapper that is built and maintained by my good friend Ima Genius. It has been a useful tool in helping people recover lost property. There is one minor pitfall to it, though. People tend to build... a lot. Some people have built upwards of nine million objects in AlphaWorld. That's a crazy huge number. If you've even built a few thousand objects, sorting through the list of objects can be quite time consuming and daunting, trying to find that one object that belongs to some long-lost build you built some time in the past.
Over time I've kept thinking that there must be a solution. There must be a way to group these objects into things that are likely to be distinct builds by you, so that you can just look at the groupings and go visit each one, instead of trying to filter through a list of objects. I started researching and learning. I finally came across what I believe to be the answer: Cluster Analysis.
Cluster analysis is where you take several points in space and using one of the many different cluster analysis algorithms you classify them by some potential logical grouping. This sounds exactly like what I want to do for AlphaMapper.
Last night I took some time off from the main AlphaMapper code to prototype a cluster analysis algorithm. Using some randomly generated cluster data, I was able to identify clusters with ease. The particular algorithm I picked has some short comings, but there's a better version of this algorithm that I plan to implement for AlphaMapper.
 |
| Results of Cluster Analysis |
As you can see in the image above, clusters that should logically be considered contiguous are some times being split into two separate clusters. These clusters tend to be overlapping clusters with odd shapes and densities that don't quite match the other clusters. This is something I plan to fix for the eventual introduction of this feature in AlphaMapper; however it is something that can most likely never be completely fixed due to the nature of the data and this class of algorithms.
So, now that I've identified clusters, what can I do with them? The idea is to take the set of points for each unique cluster and run it through another type algorithm called convex hull which is a way of taking a set of points and finding a convex polygon that best fits around the given set of points. I can then take the polygons output by this algorithm and store their points in a database and relate all of the objects contained inside of them to the polygons.
This is where the fun begins. Having this location data and polygon shapes a user can go to AlphaMapper and display these polygons on the map to indicate places that are most likely to be distinct builds that they've made in the past. They will overlay the map much like the roads do on Google Maps. This way you can see how they relate to the objects under them.
Another cool thing that I can then do, is that since I've related these polygons to the objects that are contained within them, I can make it so that you could search for specific object types, descriptions, actions, etc and get back only those likely builds that contain those specific types of objects.
Another nice thing about the algorithm I am using, is that it can also get a list of those points (objects) that don't belong to any specific cluster (build) and store them. So this way a user could also find all objects that they've built that aren't a part of any specific build. This can help them locate lost seed objects and such.
There's a lot of potential in this system and this is merely the tip of the iceberg for the things that I am capable of getting from all of the objects found in AlphaWorld. There are certainly other useful things I may be able to extract from the data to help users of AlphaMapper better use the mapper and interact with it in ways that weren't previously possible with either the old AlphaMapper or AWPS alone.
I'd also like to make a privacy note. Many builders are concerned that others will be able to find their secret builds. This will not be the case with AlphaMapper and what was discussed in this article. Only you (or anyone you give permission to) will be able to view your own property and builds mashed up against the maps. There may be certain exceptions to this rule for historical reasons (i.e. citizens who no longer use AW or have passed away).
Sunday, November 13, 2011
Functional Mapping
I am back to work on AlphaMapper once more, after reaching a point where I felt like I had to take a break last time.
One of the biggest missing pieces in finishing the mapper is the ability to parse out action commands and use them to help with rendering the maps. We all know that action commands are extremely important to how ActiveWorlds works. They're used heavily in AlphaWorld to change the appearance of objects. Everything from the color and texture of an object to the size and shape of the object.
Thus they are extremely important to AlphaMapper. If the objects didn't appear on the map as they do in Alpha World, they would extremely odd on the map. So, I've started building a way to take the action command text and turn it into something I can use to help make the objects appear as they do in Alpha World.
For this task, I'm using a programming language called F# which is related to C# (the language the majority of AlphaMapper was written in) in that it is also a .NET language. They have some similarities, but F# is what is primarily called a functional programming language which takes a very different approach to programming. Instead of being made of sub-routines and sequential calls, the program is made up of functions that can be manipulated like any other data in the language. The language has very few side effects (and is thus easy to make parallel) and relies heavily on recursion to process data.
This particular type of programming is very declarative in nature (you express what you want and not how to do it). It is extremely well suited to building parsers with a minimal amount of code. For instance the code to actually parse action commands currently stands at 76 lines of code, including comments and white space. That's substantially less code than any C# equivalent for how the parser is currently doing.
One of the biggest missing pieces in finishing the mapper is the ability to parse out action commands and use them to help with rendering the maps. We all know that action commands are extremely important to how ActiveWorlds works. They're used heavily in AlphaWorld to change the appearance of objects. Everything from the color and texture of an object to the size and shape of the object.
Thus they are extremely important to AlphaMapper. If the objects didn't appear on the map as they do in Alpha World, they would extremely odd on the map. So, I've started building a way to take the action command text and turn it into something I can use to help make the objects appear as they do in Alpha World.
For this task, I'm using a programming language called F# which is related to C# (the language the majority of AlphaMapper was written in) in that it is also a .NET language. They have some similarities, but F# is what is primarily called a functional programming language which takes a very different approach to programming. Instead of being made of sub-routines and sequential calls, the program is made up of functions that can be manipulated like any other data in the language. The language has very few side effects (and is thus easy to make parallel) and relies heavily on recursion to process data.
 |
| Example of F# code from AlphaMapper |
I have this parser producing what is called an Abstract Syntax Tree which is a data structure that represents the minimal information needed about the parsed data to appropriately reason about it. Essentially the tree is a list of the different triggers (and any associated data in the instance of the at and zone triggers) which then contains a list of commands associated with each trigger. The commands contain all of the required data for that command and then a list of all the optional pieces.
Once I finish up the parser, I will be able to then feed this Abstract Syntax Tree into another set of functions that will walk the tree and process it to get information about how to modify the object so that it can be made to appear correctly on the maps. This is something that F# is also extremely well suited to do, also. I can essentially pass the action command into the F# code, which will run it through the parser and then walk the tree to extract information about the commands that appear on the object like the move, scale, shear, and color commands. This code will then hand back to my C# code some data that C# can work with easily to make the object appear correctly on the map.
That's another great thing about F#. Even though it is an entirely different paradigm than what C# is, it plays very nicely with C# and all of the other .NET languages like IronPython and Visual Basic.NET. All languages in the .NET family of languages share a common core that allows them to easily interact with each other (for those of you who use my .NET SDK wrapper with VB.NET, you already know this). This made F# not only well suited to writing my parser, but well suited to interfacing any of the code I wrote in F# with my C# code.
So right now, I am making significant progress towards extracting information from action commands (which I may be able to actually do more than I originally planned, because the parser is extremely robust) and using that information to make the maps appear correct. Stay tuned for more blogs!
So right now, I am making significant progress towards extracting information from action commands (which I may be able to actually do more than I originally planned, because the parser is extremely robust) and using that information to make the maps appear correct. Stay tuned for more blogs!
Tuesday, August 30, 2011
Maps!
How about some pictures?
Definitely keep an eye out, because things are getting exciting! We should hopefully have new maps before the end of the year. Once that's done, I can focus on new UI capabilities for the map application itself. Then I can return to focusing on the graphical capabilities of the new rendering engine for AlphaMapper and getting things like shadows, zones, and lights working.
As you can see, I've successfully mapped out the original AlphaWorld Ground Zero area. Great stuff! There's a few things, though. First off, this is only from a prototype. I can't render all of AlphaWorld yet. I specifically chose AW GZ due to its distinct lack of most of the advance action commands like move, rotate, scale, and shear.
If I were to try and render something like SW City Town Square Park, it would look absolutely terrible on the maps. I still have to build an action command parser to get the appropriate information out of the objects so that they appear correctly on the map in terms of position, rotation, texture, color, scale, shear, and skew. So, we're still a bit off from having full maps of AlphaWorld, but these images show that the technology I've been building over the past year works as one would expect it to work!
Also, you may notice the distinct lack of shadows. At this time, shadows have been removed. I was having troubles with them appearing on the map correctly and decided that it would be in the best interest of the project to delay them until a future version.
Definitely keep an eye out, because things are getting exciting! We should hopefully have new maps before the end of the year. Once that's done, I can focus on new UI capabilities for the map application itself. Then I can return to focusing on the graphical capabilities of the new rendering engine for AlphaMapper and getting things like shadows, zones, and lights working.
Thursday, August 25, 2011
AlphaWorld Property Import Aborted
So,
I was in the process of importing the most recent propdump of AlphaWorld into my database, when I ran into an issue. The library I'm using to insert data into the database generated a duplicate primary key. This was around object 93 million or so. This brought the whole thing down.
Fortunately, the data I had inserted is still there. The database can handle that issue just fine. So, I'll be able to use that to make progress on AlphaMapper. Still on track for hopefully getting some initial test maps out this weekend.
So... I was wondering how a duplicate key could be generated. The specification for the key type on the MongoDB website showed an exceptionally low probability of this occurring. So, I got to looking at the soruce of the library I was using. There's a bug in it that has the potential to generate the same key every 24 hours (as it did).
I'm now abandoning this library and switching to the official library. The conversion won't take very long and I should be back to loading the entire AlphaMapper propdump by tonight.
I was in the process of importing the most recent propdump of AlphaWorld into my database, when I ran into an issue. The library I'm using to insert data into the database generated a duplicate primary key. This was around object 93 million or so. This brought the whole thing down.
Fortunately, the data I had inserted is still there. The database can handle that issue just fine. So, I'll be able to use that to make progress on AlphaMapper. Still on track for hopefully getting some initial test maps out this weekend.
So... I was wondering how a duplicate key could be generated. The specification for the key type on the MongoDB website showed an exceptionally low probability of this occurring. So, I got to looking at the soruce of the library I was using. There's a bug in it that has the potential to generate the same key every 24 hours (as it did).
I'm now abandoning this library and switching to the official library. The conversion won't take very long and I should be back to loading the entire AlphaMapper propdump by tonight.
Tuesday, August 23, 2011
Storage Lockers
I've finished up the renderer to a point that I'm mostly comfortable in its abilities to render maps. There may be a few more issues that arise in the process of getting the maps to render correctly, but I will address those as they arise.
Today I want to talk about some back-end portions of AlphaMapper. AlphaWorld is a huge world, filled with hundreds of millions of objects. As of the last propdump we received, AlphaWorld contained 223,126,339 total V3 objects. The propdump file itself is over 16GB in size. So storage is a bit of an issue.
The old AlphaMapper used MySQL to store this information; however MySQL has several drawbacks and won't fully meet the needs of many of the things I plan to do with AlphaMapper in the future. MySQL is what is called a relation database. This form of database works just fine for many applications and is the preferred database type for storage of information.
AlphaMapper doesn't need a full-fledged relational system. So I'm planning on using MongoDB which is a type of NoSQL database which will work rather well for the sort of information being stored by AlphaMapper. It will also give me certain performance characteristics that I find desirable for how I plan to pull data from the database for AlphaMapper.
The biggest issue is that I will have to write a custom application for loading propdumps into the database. This shouldn't be too hard as the propdump format is well documented. It is essentially a line-by-line parse of the propdump and storing each individual object in the database.
Once I have information in the database, I can begin work on pulling it out of the database and sending it off to have the action commands parsed and the objects prepared to be fed into AlphaMapper. Getting the data out will be relatively simple. I plan to make an action command parser that essentially does nothing (no actual command parsing), but directly output the objects to be rendered by AlphaMapper. This will help me verify that property data is coming through correctly and will allow me to render simple scenes in AW, like the original GZ area.
This means updated maps are starting to become a reality. Once I can render basic map tiles, I plan to go through each and every action command that I plan to support in AlphaMapper and implement each one with all of its associated caveats. As I implement these, it means the map will start render objects with proper location via indefinite move commands, proper scale via the scale command, correct textures through texture and animate me commands, and even support for the new shear and skew commands.
Once the action command parser is done, AlphaMapper will be ready to start generating production level maps.
There's still a lot of work to be done, but with the renderer done... each step I take, puts all of us that much closer to being able to enjoy updated maps.
The old AlphaMapper used MySQL to store this information; however MySQL has several drawbacks and won't fully meet the needs of many of the things I plan to do with AlphaMapper in the future. MySQL is what is called a relation database. This form of database works just fine for many applications and is the preferred database type for storage of information.
AlphaMapper doesn't need a full-fledged relational system. So I'm planning on using MongoDB which is a type of NoSQL database which will work rather well for the sort of information being stored by AlphaMapper. It will also give me certain performance characteristics that I find desirable for how I plan to pull data from the database for AlphaMapper.
The biggest issue is that I will have to write a custom application for loading propdumps into the database. This shouldn't be too hard as the propdump format is well documented. It is essentially a line-by-line parse of the propdump and storing each individual object in the database.
Once I have information in the database, I can begin work on pulling it out of the database and sending it off to have the action commands parsed and the objects prepared to be fed into AlphaMapper. Getting the data out will be relatively simple. I plan to make an action command parser that essentially does nothing (no actual command parsing), but directly output the objects to be rendered by AlphaMapper. This will help me verify that property data is coming through correctly and will allow me to render simple scenes in AW, like the original GZ area.
This means updated maps are starting to become a reality. Once I can render basic map tiles, I plan to go through each and every action command that I plan to support in AlphaMapper and implement each one with all of its associated caveats. As I implement these, it means the map will start render objects with proper location via indefinite move commands, proper scale via the scale command, correct textures through texture and animate me commands, and even support for the new shear and skew commands.
Once the action command parser is done, AlphaMapper will be ready to start generating production level maps.
There's still a lot of work to be done, but with the renderer done... each step I take, puts all of us that much closer to being able to enjoy updated maps.
Monday, August 22, 2011
Back in Action!
Well, I'm back from my weekend trip and ready to get back to work on AlphaMapper once more.
I've declared the renderer to be in a finished state and ready to move forward. I will only be revisiting it to fix any bugs that may arise in the process of working on the next milestone. I will also revisit it for future versions of AlphaMapper to make graphical, architectural, and performance improvements. I don't see the need to apply these sort of changed at this time, because I don't even know if I need them. I know the renderer is in a state that I'm confident that it can render AlphaWorld. There will obviously be upgrades to the graphical capabilities in future versions. Things like zones, create light, and terrain. Many of which I already have a design planned out for.
The next step, which I hope to get a start on tonight, will be getting property data out of the database to be prepared for AlphaMapper. The idea is that I'll be pulling property data in a background thread. This data will then be passed off to another thread that will process all of the action commands and construct the final scene for rendering. Then the main thread will pull the processed property data in and load up all of the necessary resources into video memory and render the scene accordingly.
So, hopefully over the next few weeks, I'll be able to start pushing out test map renders. Up until this time, I've been constructing artificial scenes and rendering those to help test my renderer. I think it is about time that I start passing real world data to the renderer.
Another thing I wish to discuss is how I plan to handle create picture. It obviously doesn't make sense to handle every create picture in all of AlphaWorld. There's a few problems with that... things like broken links or inappropriate picture content. So what I'll be doing is creating what is called a white-list. The idea here is that people will submit picture paths (like the SW City texture path) to the AlphaMapper project for approval. Once the picture path is approved, it will be used to download pictures and apply them as textures in the scene as needed. This means that builders that have their picture paths approved will have their custom textures rendered in AlphaMapper. If you don't want your textures rendered in AlphaMapper, simply don't submit. The default textures for that object will be used, instead. This system will help prevent inappropriate content from getting into maps and help AlphaMapper run a bit quicker, because it won't be trying to download every picture ever used in AlphaWorld.
Anyway... keep an eye out on here, on the forums, and on Facebook. There should be interesting pictures making their way to you soon enough!
I've declared the renderer to be in a finished state and ready to move forward. I will only be revisiting it to fix any bugs that may arise in the process of working on the next milestone. I will also revisit it for future versions of AlphaMapper to make graphical, architectural, and performance improvements. I don't see the need to apply these sort of changed at this time, because I don't even know if I need them. I know the renderer is in a state that I'm confident that it can render AlphaWorld. There will obviously be upgrades to the graphical capabilities in future versions. Things like zones, create light, and terrain. Many of which I already have a design planned out for.
The next step, which I hope to get a start on tonight, will be getting property data out of the database to be prepared for AlphaMapper. The idea is that I'll be pulling property data in a background thread. This data will then be passed off to another thread that will process all of the action commands and construct the final scene for rendering. Then the main thread will pull the processed property data in and load up all of the necessary resources into video memory and render the scene accordingly.
So, hopefully over the next few weeks, I'll be able to start pushing out test map renders. Up until this time, I've been constructing artificial scenes and rendering those to help test my renderer. I think it is about time that I start passing real world data to the renderer.
Another thing I wish to discuss is how I plan to handle create picture. It obviously doesn't make sense to handle every create picture in all of AlphaWorld. There's a few problems with that... things like broken links or inappropriate picture content. So what I'll be doing is creating what is called a white-list. The idea here is that people will submit picture paths (like the SW City texture path) to the AlphaMapper project for approval. Once the picture path is approved, it will be used to download pictures and apply them as textures in the scene as needed. This means that builders that have their picture paths approved will have their custom textures rendered in AlphaMapper. If you don't want your textures rendered in AlphaMapper, simply don't submit. The default textures for that object will be used, instead. This system will help prevent inappropriate content from getting into maps and help AlphaMapper run a bit quicker, because it won't be trying to download every picture ever used in AlphaWorld.
Anyway... keep an eye out on here, on the forums, and on Facebook. There should be interesting pictures making their way to you soon enough!
Subscribe to:
Posts (Atom)