Hey everyone, I''m posting this to get some feedback... I wrote a base class for the A* algorithm, so that people can use it in their games for pathfinding. Since some of the practical details vary from game to game, my class is just a base class, but you can easily derive your own class to suit your needs. I''ve already used it to create a tile-based pathfinding class which can easily be adapted for any game which uses a rectangular grid of tiles. Anyway, since A* seems to be a recurring topic in AI programming, I thought I should release the code for whoever wants to use it. What do you guys think? Also, does anyone have any ideas for other kinds of AI tools that would be useful in your own games? Thank you very much! Rajan

Could you expand your class to permit the use of callback functions that define the specific functional tasks within the domain that the A* algorithm needs? In that way there would be no need to derive a specific class for each game... just set up the requisite callbacks, register them and go for it?

Just a thought...

Timkin

Hmm.. I did consider this at one point but there were a couple of problems with it.. The biggest problem was that my class relies on a hash table (for efficiency) which is based on the "point" structure which defines a node in space. So my class requires the client to write a function to calculate a hash value. For example, for my tile-based A* class, the locations are (x, y), so the hash calculation is:
hValue = x + y * width

Since I wanted to add a "width" variable to the Tile-based class, I had to make the hash function a member function so it has access to the width variable. If I were to use a function pointer, then I''d be pointing to some function outside of the class, so it wouldn''t have access to the width variable. Of course, the easy way out of this is to just access the width as some global variable, but I thought this would be kind of bad style since it breaks encapsulation.

So anyway, you might be right... maybe asking people to derive their own class is asking too much. I Think I can probably avoid this if I can find a way to get around having them specify a hash value. If I could assume that the Location structure that they are using doesn''t use any pointers, then I could probably just compute some hash value directly from the Location structure.

Having no pointers means that the same location will be bitwise identical... Although I have no way of knowing the members of a particular location structure, I can compute sizeof(Location), so then I can just go through all the bytes of the structure and use them to compute some arbitrary hash value. This value wouldn''t be as good as one the client could provide but it would save some work for them...

Anyway thanks for the tip, I guess I''ll have to think some more on this one to get it to be easier...

Rajan

quote: Original post by RajanSky
Since I wanted to add a "width" variable to the Tile-based class, I had to make the hash function a member function so it has access to the width variable. If I were to use a function pointer, then I''d be pointing to some function outside of the class, so it wouldn''t have access to the width variable. Of course, the easy way out of this is to just access the width as some global variable, but I thought this would be kind of bad style since it breaks encapsulation.

I''m certainly no C++/object oriented guru, but you could define the hash function as a friend function of the class, thus permitting access to its data attributes. Check out your favourite OO programming manual.

As for using a function pointer, that''s not necessarily a bad thing, so long as you test whether the function exists before trying to access it. Just as in OpenGL one must write certain functions before using the library, so to you may require the writing of certain functions - like a hash function - before your class can be used??? I''m sure if you asked the guru''s in the programming forums they would provide you with some excellent ideas for optimising your class!

Good luck,

Timkin

I just finished up my A* class thursday and the method I used was the same (value =x*maxwidth+y) however instead of using the pathfinding algo to determine collisions/cost it used the map class which was passed to it.

So basically the map class handles all the rules, max height/width ect and the A* just handles making the path based on input from the map class. Then to use it in the actual game I just give it the map, x,y,dx,dy and it returns the distance. Because of how the rules are set up, it doesn''t even need any bounds checking. If it tries to go outside the confines of the map the map rules return an impassible value and A* by design tries another way.

Also, mine is for hex based maps, not square. Very small difference (6 nodes instead of 8). It would be trivial to allow for both.

It would be nice to make your class public (mine won''t be for awhile because it''s not documented yet) but you''d need to make sure it doesn''t contain any rules within itself for determining passiblity because not every game has the same rules.

Ben


IcarusIndie.com [ The Rabbit Hole | The Labyrinth | DevZone | Gang Wars | The Wall | Hosting ]

quote: Original post by Timkin
I''m certainly no C++/object oriented guru, but you could define the hash function as a friend function of the class, thus permitting access to its data attributes. Check out your favourite OO programming manual.

I don''t think so. The hash function is provided at runtime. Hence, it cannot be declared as a friend of the class.

quote: Original post by RajanSky
Since I wanted to add a "width" variable to the Tile-based class, I had to make the hash function a member function so it has access to the width variable. If I were to use a function pointer, then I''d be pointing to some function outside of the class, so it wouldn''t have access to the width variable. Of course, the easy way out of this is to just access the width as some global variable, but I thought this would be kind of bad style since it breaks encapsulation.

Why don''t you require the functions to take three arguments (x, y, width)? You could also pass the address of the object, which could have a method GetWidth().

And no 21st century generic library would be complete without templates... I''m quite interested in AI libraries. I''d love to take a look at your code.

Cédric

Wow, so many responses- thanks everyone!

<>
Yeah, as Cedric said, I don''t think that would work although that''s a good idea.. The main problem is that making a friend wouldn''t provide any information as to which particular object''s data needs to be evaluated.

About function pointers- I do use them a little bit in my tile-based derived class, although it''s not really used in the base class because I wanted to make it flexible, and the problem with function pointers is that you can''t point to a non-static member function. That''s basically my big problem...

Ben, wow it''s cool to hear from someone else who''s also making a class like this. Yeah I really *wish* I could do something like have a "map class" but the thing is that my A* class is so generic (it uses templates) that it could work for anything from a 2D tile-based game, to an isometric game, 3D game, basically anything, since all it implements is the guts of the A* algorithm and it leaves the rest of the details up to the user.

Cedric, nah I can''t do anything specific with "width" since my base class doesn''t use a width variable. It''s templated so as I said above in this post, it can be used for *anything*. Anyway if you''d like to see the code, that would be great- maybe you could point out some things I could improve... I''ve posted a demo of the program, along with some code, at this address:
http://www.ews.uiuc.edu/~rsharma/AStar/astar.zip

You need Visual C++ OpenGL to run the demo since it actually shows a graphical depiction of the algorithm running. Also there are some openGL calls within my A* class- so of course these aren''t part of the code, they''re just in there for the sake of the demo.

Anyway I''d really appreciate it if anyone wants to take a look and let me know what you think.. If you want to contact me, my e-mail is RajS20@aol.com.. Thanks!

Rajan

You might want to look at functors, because they can retain a state. Width could be a variable in the hash functor passed to your class.

quote:
and the problem with function pointers is that you can''t point to a non-static member function

You can, but the syntax is a little bt tricky:

class A{public: void foo(){}};
void (A::*mem_fun_ptr)() = &A::foo;

I''ll take a look at your code as soon as I find some time.

Cédric

Thanks for the ideas Cedric... Yeah actually I did know about the syntax you used for pointing to a non-static member function... but I mean, in your example, you need to know the class ("A" in the example) but I don''t even know that much... Maybe I''ll look into functors, since they did turn up somewhere when I was looking around for information on how to get around all this pointer problems... I won''t have time to learn all that now though but maybe if I revise my class someday I''ll do that..

Thanks again!

Rajan

Templates!

class A{public: void foo(){}};templateclass AStar{   public:      void (X::*mem_fun_ptr)();      AStar((X::*f)()):mem_fun_ptr(f){}};AStar astar(&A::foo); 

I''m convinced that there is a lot of potential for templated artificial intelligence libraries (AITL), but it would take a lot of work to do it right, and you seem busy. If you have some free time on your hands, take a look at Modern C++ Design. boost.org is also a very useful library of generic tools, but I''m not very familiar with it.

Cédric