Tag Archives: Quantum Library

Raycasting for the Dijkstra Algorithm

Posted by santosj on April 28, 2007 Comments Off

I think I finally understand what I’m doing incorrectly with the Dijkstra implementation. I’m not using edges, part of which because there aren’t any, and traversing each node. I’m also trying to use a tree where a queue is called for.

The code I have now would work great for the A* algorithm, so I plan on keeping it and probably implementing the A* algorithm while I finish up what I have so far.

Mgccl tuned me into a link that helped me out a great deal in understanding a better solution to the problem. Fundamentally, the solution is the same. Cast a “ray” or a line towards the end node and keep doing so either until you bypass any blocked paths or reach the end.

Casting Rays

This would meet the requirements for the queue as the completed ray can be placed in the queue. Since the rays are weighted edges, it meets the final requirement for what the algorithm calls for.

The speed should increase slightly since I will only be checking the nodes that is within the ray. The worse case is that I do end up checking the majority of the nodes and not find the end. The best part is that it would allow me to traverse the same nodes more than once. The second best part is that it won’t change the API for users.

What is a Ray?

Just a line. Actually, ray casting has more origins in 3D gaming, but the goal is to have the algorithms support 3D as much as possible. It is useful for collision detection, which is what I’m using it for in this case. I’m sending a ray out and checking to see if it hits something and then sending another node out.

There is going to be a bit more mathematics involved as I need to keep in mind that I don’t want to extend further than the end node and want to move towards it as much as possible.

Similarities to A*

Hmm, in which case the algorithm will look a lot like A* at the end, but the only difference is that the Dijkstra will use rays and the A* will traverse nodes. Which has the better advantage will be up to the developer. Hopefully, by the time the algorithms are stable along with the Quantum Library, both algorithms will function as they are meant to. I fear however that the Dijkstra will be quicker for some cases than A* just because of how it is implemented. A* should be more accurate at the beginning in its path creation.

Time?

The goal was to have the Dijkstra finished by the end of the month, along with a lot of other Astrum Futura features. I don’t think I’ll be able to make that goal with the changes I have planned. The good news is that A* is closer to being implemented. The bad news is that it probably take another week or two, because I nearing the end of school and have a lot of final projects that I need to work on instead of this one.

Possibly Related Posts:


Dijkstra Bug: Deadends and Really Bad Algorithms

Posted by santosj on April 23, 2007 Comments Off

I should point out that it isn’t the algorithm for Dijkstra that is wrong, because tests show that the algorithm does what is expected. It is the internals of the Abstract (Ai_Pathfinding_Abstract) which completes both the Dijkstra and, when finished, the A* algorithms. The only reason the first (and only) test was successful was because there were no “deadends” internally.

(Some days I wish I was more intelligent, such solutions would come easier than and such problems would never had existed.)

A deadend is where the algorithm comes across neighbor nodes that had already been checked or have higher fitness than the current node. What is happening is that a deadend is being found after each iteration, which isn’t supposed to happen. The “Solution”, which is wrong by the way, is to rewind back to any available node and start over from there. It explains why the algorithm will “jump” from one point to another, instead of the correct moving along to the next neighbor.

The correct solution has always been to save each node path and then then move back when a dead end was reached until the end was reached and save that and every path that completes. The solution involves a tree data type. The solution before was more a queue which was incorrect.

I’ll have to spend some time testing and developing a tree based solution. Should be fun. Also the internals will also have to be changed, the API won’t change. I’m thinking of breaking the algorithm into three methods, one for the algorithm specific code, one to build the tree, and the last one to traverse the tree and pick the correct path. I’m thinking of keeping all of the completed paths and allowing them to be accessed by the user. What this would allow is choosing the best path instead of the shortest.

Metrics

I need to think about adding metrics to the algorithm, which would help make it more complete. Right now the only metric is the distance between the node and the end node. There needs to also be metrics for depths (3D terrain heuristics), choosing “jumps” (wormholes, portals, etc), and different types of terrain (such as moving through water would be slower or faster for certain types).

My main focus was to first get the algorithms working and then go back and allow “advanced” features to be implemented. Not that I’ll be doing all of the work, or maybe I might, but really to allow others to go in and add their own metrics.

I think if I can get the tree done, I can do a better job of allowing metrics. The API would have to change when I do.

Possibly Related Posts:


Agenda for April

Posted by santosj on April 2, 2007 Comments Off

Fixes for Dijkstra algorithm and starting A* algorithm

Well, the boundary problem has been fixed, but now the algorithm is broken and it should take some time to fix that part. I figure that while I’m doing that, I can start on the A* algorithm and try to complete that piece also. It should take a few days to complete both of them. I’ll have to rewrite parts of the Dijkstra algorithm and apply those to the A* algorithm.

Astrum Futura

I’ll want to work on the installer and get more parts completed for this. I think I’ll work on it in between other parts of the code. Really, I need to do some more research on how others do this before the product is released. I wanted to had gotten to it in mid-March, but never got around to it. I am in the game for this month and already started, which is a good thing. The Quantum Game Library is a good motivator.

The other parts for Astrum Futura will be other small enhancements and shouldn’t take more than a week. That is, if kept to a schedule and I do plan to, after I get worked up to one.

Computer Upgrading

It really depends on how much I can spend on computer parts. I might use credit for paying for the components, but I want to try to use cash. I already have plans to buy RAM sticks, either two or three depending on how much I can afford to spend. This would either put me at 3GB of total RAM or 4GB of total RAM. Depending also, I do want to look at buying Hard Drives instead. 400GB Hard Drives are closer to $100, so two would be $200, which would be around the same price as 3 1GB RAM sticks. Really, I have to decide whether I want to install windows and move files from my other drives or if I want to have 3GB of RAM.

If all else fails, I’ll just wait until May and buy both components. Not such a big deal, but the sooner I buy the drives, the sooner I can test my other drives to make sure they are really “broken” and it wasn’t just my motherboard acting up. I’m glad I kept all of my hard drives after all. The mirrored configuration should be interesting however.

Probably decide when I get my check and see how much I can spend. The RAM however won’t do me any good until I get Vista and the TV Tuner, so most likely the Hard Drives, unless I can’t afford it, then I’ll just buy the RAM after all.

Possibly Related Posts:


QGL and Astrum Futura Tracker Coming

Posted by santosj on January 31, 2007 Comments Off

I’ve been waiting for this for some time, as I’ll get an idea but not have it detailed enough to post to the forums. It has also been needed for the past suggestions and for future suggestions. The forums are great for discussion as tracker comments are just like blog comments, which are difficult to follow and see if there is a new comment on.

As a whole, I would like to add some of my own, but spending a week or so going through the old discussions might be fun! Some of the new people (Tirellco and Cyberlot) had some great comments that would be worth tracking. That said, there also has to be a formal written proposal to go along with the feature ticket, unless dependency ticket tracking is a feature of the tracker.

The ticket would have a summary and have a link to the wiki page with the full proposal which had thus far been agreed on or discussed to conclusion. It would be nice to have some sort of roadmap for which to show people (and myself) with both QGL and Astrum Futura.

I should Admit That…

I do create tickets for the sake of saying that I’ve completed that task and record that I completed that task. That might not always be the best method when you are working with other people and probably will have a lot more users submitting tickets for defects or features.

So, that is why most of the ticket proposal would be at the wiki and just have a summary at the tracker. If needed and the task is something important and would take more than several hours, it might also be good to mark that ticket in the wiki and as an dependency in the comments (or use the feature if supported).

The Fun Stuff

Mostly, it would be worth going through the old discussions and sort of “close” them and redirect to the tracker and wiki. The discussions wouldn’t be closed, as in forum moderation speak, but really to head it off into a new direction based on what is in the wiki and tracker.

Not quite sure if the update should be posted to a single sticky thread or to each individual thread.

Possibly Related Posts:


Quantum Game Extension Roadmap

Posted by santosj on January 11, 2007 1 comments

Yeah, I did come up with a roadmap, while I was developing the initial pieces right now. I’m thinking the parts that I have now should compile, but I’m not going to test that theory until I have a little bit more to show. I am however about to commit the pieces I have before I head off to sleep. I’ll see what damage there is when I wake up.

Version Convention

Major.Minor.bug/security fixes

I’m not going to bump the minor release version just to fix a couple of bugs. Only when the extension falls behind of the library release.

New Name (Kind of)

I decided to call the extension of the Quantum Game Library the Quantum Game Extension. The old name, Quantum Game Library Extension, which I was using was a little bit too long. I think QGE and QGL would be better than QGLE and QGL as it would seem to some people that QGLE extend the user land library with extra components.

Don’t want that.

Version 0.1

The first version will include all of the working trunk classes and interfaces (interfaces first) in the Quantum name space. The reason for this is that I feel the AI name space is still somewhat unstable with what only the Dijkstra pathfinding algorithm being done. I was thinking of adding the Ai_Pathfinding class, but I think that I’m going to remove it in a later refactoring of the path finding classes.

I like what I currently have and I spent a good 5 hours total now. There are a few questions that I have and need to do more research later on what the solution might be. Basically, I need to know if I add the classes to the function part or just in the INIT_CLASS_ENTRY part. It would be nice to know for sure to fix that bug before it even comes up.

Extension Constants

The PHP extension will have constants for which the user land will be able to check for. The goal is to have the extension completely replace the library and the user would need to check for the extension before including the library.

if(!isset(QGL_VERSION) && QGL_VERSION >= 0.1)
{
    // Add autoload or add library_path
}

The usage of the version numbers for the extension is that it would be difficult to keep the extension and library sync since they share the same repository if the repository revision number was used instead. It was an option I had in mind. It should only take a little bit extra work for the developers to look up that this extension version relates to that trunk revision or stable release.

In the future I would want to have the versions relate to stable releases. Only so much can be written for a PHP game library. I think bugs in the extensions and library might also relate to the version changes.

Oh, the whole reason for the version is so that if the extension is too old, then the library should be used instead. It would be slower yes, but it seems that it would be more difficult to keep an extension updated than a library.

Version 0.2

Will include any bug fixes of the library and in the extension. It will also include any new or improved Quantum name space classes that might of been developed between the time of version 0.1 and 0.2.

The major focus will be the inclusion of the AI components. If the path finding classes are complete, then I’m going to add them here and I hope to have the fuzzy logic classes finished so I can also add them.

There might be a couple of reasons why I wouldn’t release this version without the AI classes.

  1. If the Quantum name space sees major refactoring.
  2. If there is a surge of new Quantum components.

Summary

Version 0.1: Trunk up to the completion of converting code.
Version 0.2: Anything past the trunk revision of released 0.1 extension version.

Hope that clears things up.

PS

Anyone who wants to checkout (literally) and see how poorly (I suck, I know) a job I did and give suggestions, then please do so. I could really, really (please, I beg of you) use the direction and instruction. I want to stay as far away from asking questions to the internals as possible, unless I really have to.

Oh, I haven’t been testing whether the extension will compile or run, because I’m really not as much excited about fixing all of the bugs that would come up. Better to get the skeleton done before tackling the flood of compile and run time errors. If I can get the MINFO info to come up from the command line, then I think I’m doing okay.

The less people who know I’m building an extension (that is probably beyond my ability) the better. Of course, this is a public blog, but how many people read this that isn’t on planet-php? 4, 5, maybe 6 regularly (and that is probably 2 or 3 too many). So, I’m pretty much safe until that point. Rather not face the ridicule of much better (C/C++/PHP Core) developers.

PSS

As of this writing, I haven’t yet committed the header and source file for which the extension should compile. Also I’m kind of hardcore and didn’t use the PECL_Skel or the PEAR Skel.

Possibly Related Posts:


Imperfect Implementations

Posted by santosj on January 10, 2007 Comments Off

AI

I just want to iterate that the AI in the Quantum Game Library is mainly experimental and won’t be perfect. I’ve been fascinated with AI since 2004 when I developed Mecha Asylum and tried to implement a genetic algorithm, which failed miserably, in 2005. I don’t think it is a bad thing as long as it works. Has many concepts been developed that were perfect the first time? I doubt it.

The goal isn’t to have a perfect version the first time, but only to have it working. Yes, it will mean rewrites later, but I’ll be happy with that because it would mean that I’ve learned more and gained enough experience and understanding.

I’m also hoping some brighter, more intelligent, and experienced AI developer would come along. “Build it and they will come,” they say, well I’m not quite sure about that. If it does happen then I’ll be happy with the work I’ve done and the skill sets I’ll learn from the (probable) future master.

However, I do have a second goal, which is to open the possibilities of AI to other closed and open sourced PHP game developers on using AI in their games. The QGL components are GPL, so any closed source game would need to develop their own AI library.

I have big plans with the AI components I’ll be developing and I think it will take most of the time. The more I read, the more I learn of ideas that could easily (and sometimes not so easily) be implemented to make the game seem more intelligent. Whether intelligent translates to fun is another issue that would need to be addressed.

Astrum Futura

Autonomous agents (bots) will not be part of the core of Astrum Futura. Reasons being that it would take too much processing and would not be all that great for share-hosted users. This does not mean that the option will not be available, because it will eventually be a plugin. It is that the concept of Astrum Futura is of Human interaction.

It is nice that the concept of plugins and mods almost completely devoid any hurt feelings. Any AI technique would have to be debated as to whether it would be in the core or a mod. I’m guessing that a lot of the AI functionality will be in mods, but that is fine since it will allow for fine tuning.

Which is another part of the imperfect design that I’m constantly trying to ponder. How perfectly can I implement the concept of modifications in the Astrum Futura? Not very. I don’t feel that bad however, since well, after I get it working, I’ll have the prototypes from phpBB, S9Y, WordPress, and countless other implementations to research.

Again, the goal is to implement it, test it and then develop better versions. Will it be as good as WordPress or phpBB? No, of course not, those applications have been in development for years. The idea however is to learn from those applications and try to implement something that doesn’t completely cause the user disgust. The mod system should be quite impressive and I mean to make it so.

Back to AI in Astrum Futura, it is interesting I think. My goal is to try to implement as much as I can in the core (Fuzzy Logic, Finite State Machines, behavioral patterns, Path finding) and allow further development to take place (luckily that there is QGL!). I’m most likely going to have a lot of AI based mods for which developers will be able to install.

Switching the AI topic back to the Library, I should note that some first versions might not make everything possible. What I mean by that is that I’ll be vastly inexperienced in how to implement some of the AI classes in such a way that would be usable in every situation. It is good however to be able to test how well such classes work within Astrum Futura and, in the future, the rest of the Absidon games.

The concept of learning, which I’m loving the idea of more and more, would not be something that could be a mod in some cases. The reasons is that one mod for one type of game wouldn’t be applicable to another game. There will be a mod for Astrum Futura, but it wouldn’t be compatible with a RPG game or any other game that isn’t a clone of Astrum Futura. A new mod would have to be created for that game model to simulate learning. I do want to make it as easy as possible on the front end, but the back end would be where all the work would take place.

To reiterate, don’t expect it to be perfect, but do expect it to work!

Also, thank goodness that I’m not the lone developer because I’ve never would have gotten as far as I have.

Possibly Related Posts:


Dijkstra Path Finding Algorithm

Posted by santosj on January 9, 2007 31 comments

Update March 21, 2007: Will be updated to work starting with Revision 278
Update March 31, 2007: Will be updated to work starting with Revision 285

Warning: Dijkstra is greedy; usage with large coordinate boundaries may timeout.

Even with the Singleton Dijkstra class, I still would have created my own. The reason is that I needed to create a work flow for the A* algorithm. The A* (A-star) algorithm is better as it is more efficient and only searches the nodes going towards the end node. A* is also a little bit more difficult compared to the Dijkstra algorithm. At least with the work flow, either algorithm could be used with little addition work. All the finished A* algorithm would need is to load the heuristic object along with the measure object.

Truthfully, my coding is incorrect in that it doesn’t follow the weighted edge, but instead assigns a fitness to all nodes. From my research it seemed that the edges would be assigned the distance from the start node and then the path would be traversed after.

My algorithm instead assigns the fitness from the actual distance of the node from the end node. It does not stop when the end node is reached because it needs to make sure that no other nodes could be used to reach the end, in case of a blocked path somewhere.

My Dijkstra algorithm might need refactoring later, but it works currently and that is all I care about. It seems that fudging is okay in game development, so I’m going to assume that since it harms none that it will be okay.

Read more for the tutorial on how to use the classes.
Read more »

Possibly Related Posts:


Fuzzy Logic Class Prototype

Posted by santosj on January 7, 2007 2 comments

I plan on supporting both the FCL file definitions and also objects that do the same thing. The FCL file reader object will use the other objects, so that each would complement each other.

// Variables
Ai_FuzzyLogic_Variable_Abstract();
Ai_FuzzyLogic_Variable_Input(); // Extends Ai_FuzzyLogic_Variable_Abstract
Ai_FuzzyLogic_Variable_Output(); // Extends Ai_FuzzyLogic_Variable_Abstract

Well, anything further will have to wait for experimentation, but I do have some plans as to how the execution will be.

// Rule 0;
$rule0 =Ai_FuzzyLogic_Rule
                   ->if($term)
                   ->and($term)
                   ->then($term);

Ai_FuzzyLogic::addRule($rule0);

// Rule 1;
$rule1 = Ai_FuzzyLogic_Rule
                   ->if($term)
                   ->and($term)
                   ->and($term)
                   ->or($term)
                   ->then($term);

Ai_FuzzyLogic::addRule($rule1);

I do know that the rule can be better served with this method since it has a limited set of methods that can be used together. The rest of the pieces will take a lot of thought and testing to finalize, but I think I can work out a good first API for which the user will use. I can then refactor the back end later when I think of a better method.

Possibly Related Posts:


Started Quantum Game Library Extension

Posted by santosj on January 5, 2007 8 comments

This does not mean that anything beyond having it compile will be done. I just basically want to have the initial extension building working so that work can be done later. Whenever any component enters “stable” status, it would be easier to commit it to the extension. I think that it may take a little bit of debate as to which component is stable and when. It also depends on how difficult it is to (re)write the component in C++ in the first place.

I would like a direct PHP to C++ library class translation. This means that the library (definitions) and code will basically match the PHP counterpart (except where hashes won’t be efficient). The PHP Extension part will list the classes, the methods and create the C++ library code for PHP and call the methods. So the only thing the PHP Extension code will be is using the C++ library and making it available to the userland.

If this works out well, then it might just be as quick to write the C++ code as it is to write the PHP code (just kidding, but it would be easier). After I have written enough (the skeleton), I plan on committing it to the repository. Granted, I need to have Subversion on my PC for which to commit the ext/qgl to the Quantum Game Library repository. Which is why I’m writing the extension now in the first place, that I can’t access the repository, currently.

See how far I can get before I get paid and get the parts to get my new computer. That will be longer than one week, but it should be okay given that there are some components that could be converted during that period.

PHP to C++

For efficiency purposes, really only the methods and properties will be the same. There should be a few times the code for PHP wouldn’t be translated to C++. However, the results should be the same regardless.

Later Refactoring

The road map was to start this project in March. The reasoning being that a large percentage of the library would be stable and wouldn’t be at risk of refactoring. It is unpreventable that some parts would later be refactored. That shouldn’t stop it from doing so, however the extension shouldn’t be too far behind.

There would have to be extension versions that either match the library version or a list which states which extension version matches what library version. Since there currently isn’t a version, this won’t be a problem until a release. Only then hopefully a better C/C++ developer would join.

How hard can it be? I’m being serious, I don’t want to get into it and realized that I suck. Doesn’t help that I have to relearn most things about C++.

Possibly Related Posts:


Quantum State

Posted by santosj on December 22, 2006 2 comments

It is a play on words, you see. It isn’t actually a quantum state as in quantum physics, but as in the Quantum Game Library state machine class Quantum_State. I was reading about state machines and how developers build libraries to make it easier to test, I was thinking of doing something similar for the QGL. It could also help with the Fuzzy Logic part of the AI library.

There are such things as Fuzzy States and I could either extend the Quantum_State or use its functionality to be used with the Fuzzy Logic part.

Pathfinding Update

I did some more research of the Dijkstra pathfinding class and I’m really wondering if I should include it. I could finish it, use the code to finish the A* algorithm and then move the pathfinding classes over to the Quantum Namespace. It would remove the Dijkstra pathfinding, but it would make the classes shorter.

Quantum_Path – Ai_Pathfinding_Astar
Quantum_Path_Exception – Ai_Pathfinding_Exception
Quantum_Path_Heuristic_Interface – Ai_Pathfinding_Astar_Interface
…and so on

What I have so far for the Dijkstra will be massively slow and really inefficient. Plus, it should only find one end point and not multiples like I had wanted. I believe that the Pathfinding will be due for another major overhaul before the end of this month (depending on exactly how much more work I put into the Dijkstra classes before I work on another Quantum Game Library component).

Possibly Related Posts: