Problems in Plug-in-Land
Seems plug-ins weren't as easy to get set up than I first imagined. :
Friday, April 08, 2005
Wednesday, April 06, 2005
Abstract Interfaces and Plug-ins
Just started reading stuff on abstract interfaces and plug-ins and its really getting me excited with some of the potential projects that I can convert to using these. It really is that "when you have a hammer, everything looks like a nail."
Currently, I'm thinking that the easiest thing to convert to being a plug-in would be the IDEA 3D Framework. I think I can expose the main rendering and mutation functions, which then would make it possible to write plug-ins to change the object being mutated. We can probably start by doing this statically, since only one plug-in can be in use at any given time. However, it can easily be made to be dynamic in the future for many more purposes.
I'm a little too excited to sleep just thinking about the idea, but then I'll need to sleep to have energy to work on it over the weekend.
Currently, I'm thinking that the easiest thing to convert to being a plug-in would be the IDEA 3D Framework. I think I can expose the main rendering and mutation functions, which then would make it possible to write plug-ins to change the object being mutated. We can probably start by doing this statically, since only one plug-in can be in use at any given time. However, it can easily be made to be dynamic in the future for many more purposes.
I'm a little too excited to sleep just thinking about the idea, but then I'll need to sleep to have energy to work on it over the weekend.
Sunday, April 03, 2005
Filemapping and Vectors....
Just spent the past week finishing up a generic systems module where I've encapsulated file I/O stuff for a win32 system. The key aspect of the systems module (feature) revolves around the use of filemapping when applicable. It does take up some extra memory (actually quite alot depending on file size), but it is capable of offering some very fine tuned file access capabilities. Not to mention if a virtual file system is implemented later, read and writes can happen quite fast. Of course, filemapping doesn't work everywhere, so there are provisions for a non-filemapped mode.
I started out wanting to create a template class that would store a 2D or 3D vector, but then I sort of settled on them just being of type float. I also decided on writing a TPoint2 and TPoint3 class for storing points in 2D and 3D. The TPoint# classes had point/vertex specific operation tagged onto them. Then there was the big debate on whether I should inherit the TPoint# class to create the TVector# classes. In the end, I ended up just using encapsulation instead of inheritance. On the one hand, inheritance means I wouldn't need to rewrite alot of code to create the TVector# classes, but on the other hand, it would mean that I may have to do some overloading of the methods defined in the parent class. So, in the end, I decided that using encapsulation may be better for the time being. It would be nice to be able to have one pointer pointing to either a vector or vertex based on polymorphism, but I felt that there may be some ambiguity there on my part later on as I begin to abuse that. So, for current purposes of making things clean, cut and dry, I felt that having seperate classes for vector and vertex was a good idea.
Of course, none of this code is tested either, so I'll be field testing them later with my newer and later projects.
-------------------------------
While looking around for the generic rotation matrix for rotating around an arbitrary axis, I ran across the Quaternion vs Vector debate. It was kind of interesting to read about, and I think both sides pose valid arguements. For me, however, at current stages, I still feel that vectors are easier to manipulate, since it is still a much more straight forward mapping to the 3D space we work in. I think I read one person said in his post "why create an extra dimension to make things more complicated when the 3 we have works" or something like that. Of course, there probably are other benefits to quaternion, which I will definitely look into, but as for representation, I somehow still like vectors.
I started out wanting to create a template class that would store a 2D or 3D vector, but then I sort of settled on them just being of type float. I also decided on writing a TPoint2 and TPoint3 class for storing points in 2D and 3D. The TPoint# classes had point/vertex specific operation tagged onto them. Then there was the big debate on whether I should inherit the TPoint# class to create the TVector# classes. In the end, I ended up just using encapsulation instead of inheritance. On the one hand, inheritance means I wouldn't need to rewrite alot of code to create the TVector# classes, but on the other hand, it would mean that I may have to do some overloading of the methods defined in the parent class. So, in the end, I decided that using encapsulation may be better for the time being. It would be nice to be able to have one pointer pointing to either a vector or vertex based on polymorphism, but I felt that there may be some ambiguity there on my part later on as I begin to abuse that. So, for current purposes of making things clean, cut and dry, I felt that having seperate classes for vector and vertex was a good idea.
Of course, none of this code is tested either, so I'll be field testing them later with my newer and later projects.
-------------------------------
While looking around for the generic rotation matrix for rotating around an arbitrary axis, I ran across the Quaternion vs Vector debate. It was kind of interesting to read about, and I think both sides pose valid arguements. For me, however, at current stages, I still feel that vectors are easier to manipulate, since it is still a much more straight forward mapping to the 3D space we work in. I think I read one person said in his post "why create an extra dimension to make things more complicated when the 3 we have works" or something like that. Of course, there probably are other benefits to quaternion, which I will definitely look into, but as for representation, I somehow still like vectors.
Saturday, April 02, 2005
Riding the Fitness Curve!
As a continuation from my previous rant about the obsession with A*, I decided to maybe talk about a concept for a new pathfinding algorithm/method that I've been wondering about.
For those familiar with hill-climbers, you should know that they have a nasty tendency to get stuck at a local optimal. This is uasually not a great idea, which is why Morris came up with the BreakOut method, which is great because what it does is modify the fitness plane such that a local optimal is "filled" in with penalty and the hill-climber just kind of spills out and move on to the next optimal. Thus, you will eventually reach an absolute optimal. This was a really neat little idea since it only required a breakout list that kept track of all the places you've been. The down-side, however, is that the list can get quite storage intensive in the memory if you run it for a long time, or you have a large fitness space.
Tabu search and ant colony optimization had some nice ideas dealing with memory issues. For tabu search, the lists are of fixed length and entries expire. In ant colony, the entries just lose weight and eventually disappear. So, combining these two ideas with the breakout method, you get a breakout method with a decaying penalty that eventually disappears.
So, what does this have to do with pathfinding? Well, pathfinding is just one of those funky problems that contains a few assumption that nicely helps us make the problem simpler.
In discrete pathfinding, where you have a fixed number of "nodes," you get the advantage of A* search, which is nice and optimal, until your number of nodes kind of blow up in your face and then you have to settle with sub-optimal solutions with fixed iterations of iterative deepening A* or just A* that goes n steps deep. Those, I guess we can call the n-A*. The problem gets a little nastier with continuous space, which is where games are usually going nowadays. With real space, you can't really have "nodes" to run an A* unless you assign them yourself, which really reduces the realism, not to mention the flexibility of motion. Well, you can consider shifting way-points dynamically, but still, how many people actually travel along straight lines and splines in an unknown region anyways. Even if you know where you are, there's always a small tad of randomness to your motion.
So, what about path discovery on the fly? Nothing pre-planned with a touch of randomness. Now, the assumption, of course, is that the agent has no knowledge of the terrain, only based on what is within visible range. So, combining tabu search and breakout methods, we can look at the field of play as one big fitness plane where in the beginning, the goal is the lowest point and that the agent is trying to get to it. So, with some randomness, we start moving in the direction of the goal, while leaving a traile of breakouts behind, which raises the fitness plane behind us . This will prevent the agent from actually back tracking. Then, let's say the agent sees a wall with no entrance, it then randomly chooses to travel along the wall in some direction. All this time leaving breakouts. As the agent moves farther from the initial point, the initial breakouts start to decay and disappear.. So, we will basically circles around the wall untill we find a path towards the goal to go past the wall. In a sense, we sort of just surf the fitness wave we leave behind, until we maybe hit a dead-in and turn around and backtrack . Its a little hard to fully describe this concept, but it is a pretty nice real-time pathfinding idea, which is something we use in real life anyways.
As for the other nice thing about it, all visible obstacles can easily be seen as spikes or raised areas on the fitness plane. Since the goal is the minimal, this will automatically drive the agent away from the walls for a certain distance, or follow the walls, depending on the effect.
---------------------------------------------------------------------------------
There is another simpler way too. :p
This just came to mind while thinking about evacuation modelling. If evacuation models can be used to simulate people exitting an area, why can't it be used to simulate pathfinding behaviors in real time?
So, given a goal, obstacles, and other dynamic things along the way, the agent will be attracted to the goal, but repelled by the obstacles. If say in a waze of area with rooms, we can then use the scenegraph to duplicate the attraction of the goal onto entry-ways towards it. It doesn't have to be exact, but the agent will then be able to follow these attractions and move towards the goal. The cost is almost free, and the results are dynamic.
For those familiar with hill-climbers, you should know that they have a nasty tendency to get stuck at a local optimal. This is uasually not a great idea, which is why Morris came up with the BreakOut method, which is great because what it does is modify the fitness plane such that a local optimal is "filled" in with penalty and the hill-climber just kind of spills out and move on to the next optimal. Thus, you will eventually reach an absolute optimal. This was a really neat little idea since it only required a breakout list that kept track of all the places you've been. The down-side, however, is that the list can get quite storage intensive in the memory if you run it for a long time, or you have a large fitness space.
Tabu search and ant colony optimization had some nice ideas dealing with memory issues. For tabu search, the lists are of fixed length and entries expire. In ant colony, the entries just lose weight and eventually disappear. So, combining these two ideas with the breakout method, you get a breakout method with a decaying penalty that eventually disappears.
So, what does this have to do with pathfinding? Well, pathfinding is just one of those funky problems that contains a few assumption that nicely helps us make the problem simpler.
In discrete pathfinding, where you have a fixed number of "nodes," you get the advantage of A* search, which is nice and optimal, until your number of nodes kind of blow up in your face and then you have to settle with sub-optimal solutions with fixed iterations of iterative deepening A* or just A* that goes n steps deep. Those, I guess we can call the n-A*. The problem gets a little nastier with continuous space, which is where games are usually going nowadays. With real space, you can't really have "nodes" to run an A* unless you assign them yourself, which really reduces the realism, not to mention the flexibility of motion. Well, you can consider shifting way-points dynamically, but still, how many people actually travel along straight lines and splines in an unknown region anyways. Even if you know where you are, there's always a small tad of randomness to your motion.
So, what about path discovery on the fly? Nothing pre-planned with a touch of randomness. Now, the assumption, of course, is that the agent has no knowledge of the terrain, only based on what is within visible range. So, combining tabu search and breakout methods, we can look at the field of play as one big fitness plane where in the beginning, the goal is the lowest point and that the agent is trying to get to it. So, with some randomness, we start moving in the direction of the goal, while leaving a traile of breakouts behind, which raises the fitness plane behind us . This will prevent the agent from actually back tracking. Then, let's say the agent sees a wall with no entrance, it then randomly chooses to travel along the wall in some direction. All this time leaving breakouts. As the agent moves farther from the initial point, the initial breakouts start to decay and disappear.. So, we will basically circles around the wall untill we find a path towards the goal to go past the wall. In a sense, we sort of just surf the fitness wave we leave behind, until we maybe hit a dead-in and turn around and backtrack . Its a little hard to fully describe this concept, but it is a pretty nice real-time pathfinding idea, which is something we use in real life anyways.
As for the other nice thing about it, all visible obstacles can easily be seen as spikes or raised areas on the fitness plane. Since the goal is the minimal, this will automatically drive the agent away from the walls for a certain distance, or follow the walls, depending on the effect.
---------------------------------------------------------------------------------
There is another simpler way too. :p
This just came to mind while thinking about evacuation modelling. If evacuation models can be used to simulate people exitting an area, why can't it be used to simulate pathfinding behaviors in real time?
So, given a goal, obstacles, and other dynamic things along the way, the agent will be attracted to the goal, but repelled by the obstacles. If say in a waze of area with rooms, we can then use the scenegraph to duplicate the attraction of the goal onto entry-ways towards it. It doesn't have to be exact, but the agent will then be able to follow these attractions and move towards the goal. The cost is almost free, and the results are dynamic.
