Sign in to follow this  
ollyb342

Pathfinding in a tower defense game.

Recommended Posts

ollyb342    122
Hey guys,

I've been making a 3D tower defense game with OpenGL and LWJGL (Java) and I'm at the point where I'd like to start thinking about enemies etc.

Now, I've been following [url="http://www.peachpit.com/articles/article.aspx?p=101142&seqNum=3"]this tutorial[/url] so far to learn A* pathfinding, and I'm understanding the theory well. However I'm now at a stage where I need to somehow get my 2D integer array of tile types into a load nodes with connected neighbouring nodes and I have no idea at all how to progress.

So GD.net gurus, any ideas on how I should progress?

For those that are interested, the game is currently at this stage: [url="http://img857.imageshack.us/img857/1959/loldefv10.png"]Lolliver Defense[/url]
Cheers!

Ollie.

Share this post


Link to post
Share on other sites
Brain    18906
Your two dimensional tile array is basically your nodes. Nodes is just the fancy mathematical term for the same thing, so if you allocate a set of arrays with the same dimensions as your tile map, you can use these to store the correct F, G and H values. In my own implementation last time i implemented A* i also used a list of coordinates which i then reversed upon finding the correct route, as part of findind a route is tracing a path back from where you ended up to where you start using the values in your nodes.

I can provide source code for this in C++, drop me a line if you would find that useful!

Share this post


Link to post
Share on other sites
ollyb342    122
Heyy, got it working! I'm a happy man =D

[url="http://img823.imageshack.us/img823/4240/pathfindingf.png"]Here it is! Each circle represents a node.[/url]

Cheers for the help.

Ollie.

Share this post


Link to post
Share on other sites
TheTroll    883
For the most part (there are exceptions) tower defense games have the easiest pathfinding of any game and people over think it.

Your game might be different but I am going to guess that it is not. For your monsters, they can pretty much only go in one path. Point A always leads to B, which leads to C and so on. So the reality is there is no pathfinding, it is just a array of tiles that list where they can go and in what direction. Anything else is just a lot of processing for no real reason.

Share this post


Link to post
Share on other sites
ollyb342    122
You're correct about the necessary AI being quite simple for a tower defense game.

But apart from some dodgy handmade AI I made for a pacman game I'm not that well experienced, so this was a nice introduction to more widely recognised pathfinding algorithms.

After implementing in Java now I'd definitely use it in other projects, it's amazing!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this