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.
Tuesday, March 29, 2005
The Obsession with Paths
After browsing through the GameDev.net AI forum, I've come to one conclusion, when it comes to game AI, everyone (most) are obsessed with pathfinding. To tell you the truth, I don't think much about pathfinding in the first place, considering it is one of like the first few things you learn when you take any college level AI course. Ironically, pathfinding is not that much AI than just an algorithm or heuristic to solve a problem. Hell, its more like a solution to a graph theory problem, which means its more applied math than AI. And when you talk about pathfinding, you talk about A*, which ironically is pretty dang archaic. Its a shame no one has come up with anything better, but that's not really possible, since A* is pretty optimal on its own. Technically, A* has many other merits in game theory along with other things like alpha pruning and min-max, but why every single game developer and beginner game developeris obsessed with it is beyond my comprehension.
Well, technically, I do understand why everyone is so hung up on A*, just because its optimal and fairly easy to implement, not to mention being implemented to death. A* is capable of giving you the BEST path given enough information and processing time, but the question I ask is, is it worth it? I've even heard people saying that you can just do A* to look like n steps ahead, but then.....oh well, I'd say, what's the point. There are so many other ways of doing pathfinding out there now that its actually kind of funky to be stuck with A*.
In most cases, there is no need for an absolute optimal solution. Most people don't walk straight lines towards a target anyways. So, why haven't gaming people picked up on ant colonies or tabu search even to do pathfinding? I guess some worry about computational overhead and storage overhead, etc. If you really are worried about these, then you really don't care too much about good AI. Plus, how much more space would it require? Compared to some games that have megabytes and megabytes of texture, implementing these algorithms will obly take up a few more kilobytes max of extra memory storage. Computational complexity is not an issue either. So you spare some time and crunch about 5% - 10% fewer polygons, but that's where optimization comes in on the graphics end. So you lose like 10 - 20fps in a game that runs at 120fps and where most ordinary people set their refresh rate to no more than 75Hz. Sometimes, some things just don't make too much sense for me.
"But its running at 100fps instead of 120fps, that's horrible!!!"
"Dude, the average person perceives only around 60fps and if you start seeing scanlines with your monitor set at 100Hz, you need to go outside and do something else instead of sitting in front of a monitor for 10 hours a day like me. And even I don't see scanlines at 60Hz."
But seriously though, how can we implement path finding in games with something other than A*? How do we work with Ant Colony Optimization? How do we incorporate Tabu search? What about Simulated Annealling? And where the hell am I getting these names?
More answers next time, after I finish some more coding and start procrastinating again. But don't worry, its not as bad as you think.
Well, technically, I do understand why everyone is so hung up on A*, just because its optimal and fairly easy to implement, not to mention being implemented to death. A* is capable of giving you the BEST path given enough information and processing time, but the question I ask is, is it worth it? I've even heard people saying that you can just do A* to look like n steps ahead, but then.....oh well, I'd say, what's the point. There are so many other ways of doing pathfinding out there now that its actually kind of funky to be stuck with A*.
In most cases, there is no need for an absolute optimal solution. Most people don't walk straight lines towards a target anyways. So, why haven't gaming people picked up on ant colonies or tabu search even to do pathfinding? I guess some worry about computational overhead and storage overhead, etc. If you really are worried about these, then you really don't care too much about good AI. Plus, how much more space would it require? Compared to some games that have megabytes and megabytes of texture, implementing these algorithms will obly take up a few more kilobytes max of extra memory storage. Computational complexity is not an issue either. So you spare some time and crunch about 5% - 10% fewer polygons, but that's where optimization comes in on the graphics end. So you lose like 10 - 20fps in a game that runs at 120fps and where most ordinary people set their refresh rate to no more than 75Hz. Sometimes, some things just don't make too much sense for me.
"But its running at 100fps instead of 120fps, that's horrible!!!"
"Dude, the average person perceives only around 60fps and if you start seeing scanlines with your monitor set at 100Hz, you need to go outside and do something else instead of sitting in front of a monitor for 10 hours a day like me. And even I don't see scanlines at 60Hz."
But seriously though, how can we implement path finding in games with something other than A*? How do we work with Ant Colony Optimization? How do we incorporate Tabu search? What about Simulated Annealling? And where the hell am I getting these names?
More answers next time, after I finish some more coding and start procrastinating again. But don't worry, its not as bad as you think.
Tuesday, March 22, 2005
IDEA 3D Framework
Its been a while, but I guess no is a good time to post the IDEA 3D Framework I wrote a few weeks back, like 2 I think. So what did I learn in writing it? Never show your advisor too cool an idea because you'll just end up with more work. However, seriously, this thing is pretty dang cool. Being able to mutate a chair and manipulate it in 3D is pretty cool.
Overload....
Kind of been in overload mode through the past two weeks, so never really got more programming done beyond what I needed to write those two papers. Man, I was like a paper writing machine for a while. Now that things have died down a bit, I can go back to doing a few other things I like.
Been able to field test some of the math and container modules that I wrote before in the evacuation simulation that I recently created. It was kind of a good way to see what works and what doesn't. There seem to be a few more kinks about Visual C++ that I never noticed before. Strange issues with pointers and destructors. Better look into that. But I found that one of the down side in working in Visual Studio .NET is that I've been having a hard time tearing away file dependencies with the .NET framework, even though I don't specifically use it.
Been able to field test some of the math and container modules that I wrote before in the evacuation simulation that I recently created. It was kind of a good way to see what works and what doesn't. There seem to be a few more kinks about Visual C++ that I never noticed before. Strange issues with pointers and destructors. Better look into that. But I found that one of the down side in working in Visual Studio .NET is that I've been having a hard time tearing away file dependencies with the .NET framework, even though I don't specifically use it.
Sunday, March 13, 2005
Out of the Loop....
Dang....
It's only been a week since I last worked on the VFS code and I'm already unfamiliar with it. Guess I need to take some time to sort it out again. There seems to be some memory issues with deleting a file. I'll have to take a closer look into that. For now, I think I'll let it sit a bit overnight. Been thinking about implementing a few more features.
For one thing, I need to be able to recognize the version of the VFS that was created by the VFS Generator. I may do version changes later and it would definitely cause problems if the versions weren't right, since it'll mess up the data if the format has been changed. Also, been thinking about ways to build directory structures within the VFS. Thinking about folding trees and etc, but the sticking point is how the structure is saved along with the filename. It would be nice if I could just save directory structures directly into the VFS files and not have to rely on a index file, but that has some strange issues with itself, since it effectively increases the storage overhead. Was thinking about just storing a md5 hash of the file name + path, but then retrieval would mean I'd need to undo the hash to know what's stored there, and I'd still need an index file. So....all I can say now is.......dang it......
It's only been a week since I last worked on the VFS code and I'm already unfamiliar with it. Guess I need to take some time to sort it out again. There seems to be some memory issues with deleting a file. I'll have to take a closer look into that. For now, I think I'll let it sit a bit overnight. Been thinking about implementing a few more features.
For one thing, I need to be able to recognize the version of the VFS that was created by the VFS Generator. I may do version changes later and it would definitely cause problems if the versions weren't right, since it'll mess up the data if the format has been changed. Also, been thinking about ways to build directory structures within the VFS. Thinking about folding trees and etc, but the sticking point is how the structure is saved along with the filename. It would be nice if I could just save directory structures directly into the VFS files and not have to rely on a index file, but that has some strange issues with itself, since it effectively increases the storage overhead. Was thinking about just storing a md5 hash of the file name + path, but then retrieval would mean I'd need to undo the hash to know what's stored there, and I'd still need an index file. So....all I can say now is.......dang it......
