Astar sandbox
To test my experiment with a tower defense in an AI sandbox I started by implementing some basics.
In this first step I generated a random “world” with boxes on which I implemented the famous A* algorithm. As a start the user can move around in the sandbox by clicking on the destination.
For simplicity reasons I decided to use a regular grid as a graph – this will suffice for a this experiment. Not at all fancy or anything but but here is the result of this first little step:
If I get more time, I will post on some more technical details in my implementation, for example how I used DDA for path smoothing. But I’ll have to save that for a future post.
Next step is probably to get some rudimentary bots in there, moving around. Then add physics as well. This should introduce some interesting problems with locality in the pathfinding, entities get pushed of the grid etc. Luckily I already have written a physics engine, and I do have code for bots, if not on the computer at least in my head.. somewhere.
Stay tuned!
Nice, smooth movement, would be perfect for an action shooter actually. I suppose it only works for rectangles? I sure would love some more about this DDA, some long time ago I read on your blog about Spatial Hash and I am using it regularly for my projects, so, I have to say, I consider your articles at least quite useful ;).
Hi Maurycy,
Thanks for the kind words, yes I am actually considering making a little shooter on the way! The grid I use is pretty dense, so searches would probably work ok with most “not-so-intricate-kinds-of-shapes”. This is not a solution that would work for larger maps though.
I will try to write up an article on the DDA, it’s really not complicated, but it took some time to get it right. Happy to hear that you are using the Spatial Hash! I was actually thinking of adding DDA to the Spatial Hash for ray casting queries (to avoid having to return all cells that a diagonal ray set up in for a test rectangle).
Nice page by the way, retrocade.net.
Ah, Ray Casting. I remember when I was developing a Poing clone (very nifty breakout variation, feel free to look it up: http://en.wikipedia.org/wiki/Poing_%28computer_game%29) I spent quite some battling with Rays and shape collision, trying to make them work fast AND proper. Too bad I never finished this project.
I took a better look on the DDA, and it seems I have already had a chance to use Bresenham’s algorithm, in the aforementioned project. Reinventing this idea was pretty hard, I wish I knew about it back then :).
I am afraid you lost me on the last sentence, about adding DDA to spatial hash. You mean make it part of the SpatialHash class?
And thanks for praise :).
The benefit of DDA is that it will touch all cells in its path while Bresenham may skip some (diagonal jumps, see image on http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm where some cells that the line crosses aren’t detected). DDA will include those. Haha, yes, I think I also did that once, probably at the same time I started to lose my hair 🙂
Yes, exactly, if you want to raycast from A to B, the spatial hash can first give you potential objects the ray could hit. As it’s now it will return all cells defined by the rectangle (a.x, a.y -> b.x, by) this will include lots of unnecessary cells and objects to test the ray against. Instead with DDA traversal in the sptialhash it would only return the cells in the rays path narrowing down the objects to actually test. Another idea here is to return the list of potential hit cells in line traversal order – by doing so raycasts that only are interested in the first object that is hit (e.g. a bullet) could cancel the search once a cell has been exhausted with a hit. Well, so much to try, so little time 🙂
Poing looks cool!
Oh! Traversal Order Raycast Spatial Hash (TORSH) sounds cool, but there are some problems with the implementation. If you have a big level with some walls (which are part of an good, old array, not spatial hash) the ray will go through far too many objects. This could be fixed with a custom implementation of Spatial Hash of course, which takes into consideration game-specific elements like tiles array :).
The other problem is, that if you go with TORSH and your current spatial hash implementation, you will first gather the objects and only then be able to look through and check collisions against the returned object. I suppose you could pass some kind of collisionCheckMeAgainstAn(object:MyGameObject):Boolean{} function, which would be called for each of the found object and return it if the function returned true.
As for the DDA, I had to look at it again and finally something in my mind clicked and I noticed the not-really-standard-to-wiki implementation, right in the first paragraph.
I will certainly have to add the raycasting to my implementation of the Spatial Hash if I get around to making some action game. I must say your project is shaping up nicely, but that is something I will comment on in the actual blog post ;).
About Poing – it was cool, completely something different :). If you are into olden games, I highly recommend you to try it, although it is quite difficult, like most Amiga titles.
Haha, TORSH 🙂
Yes, it’s true that you still will have to check against objects that aren’t in the hash. So far I put all of them in there, but there are probably cases as you mention with large walls that will bloat the spatial hash.
True, I think returning all the objects from the traversal is a good performance win and as you say, with a callback it will be even better. Thanks for the input!
I’m having trouble finding an online (flash, java) Poing game, do you have any link?
No flash or Java Poing, only emulator or real amiga I am afraid (game can be downloaded from aminet.net) :). I was planning to (and probably will, someday) remake this game in Flash but that is some distant future.
As for putting stuff in has, that depends on the project. I haven’t yet made a game which puts tiles into hash, but well, that can happen! I guess I just follow the old school of grid based games.