Pathfinding 2d java game?

Question

Hi all, First time on StackOverflow, keep see it coming up so thought id ask.

Im currently writing a very basic java game based on the idea of theme hospital. I'm quite new to java, currently studying at uni and in my first year. I have done java for nearly 2 years now on and off, but I'm finally devoting my time to a decent project.

Anyway sorry the question. I'm at the stage where I need to create a person (patient) to be admitted to the hospital. They need to go to the reception desk, then GP's office, and then back to their starting position. I have looked into A* path finding, but it seems really complicated to me. I understand how it works I think, but am unsure how to implement it into my game. So far, the user can place a reception desk, and build a GP's office. Each of these has a "point of usage" which will be the place the patient has to get to. The grid squares can only be full or not, there will be no different terrain.

I'm hesitant to paste any code yet, as it's messy as I've learn alot of new techniques to do with GUI in the past few months. My plan is to get to milestone 1, making the patient go to the desk then the office and then leave. Once I have this, I will tidy up the code more.

I've seen many implementations of A* and many different types. Can someone give me a starting point I can work with? Should I try and adapt an already written set of classes, or try to write my own from scratch?

Thanks in advance.

Rel

Answer 1

You do want A*, it is the optimal implementation for grid based pathfinding.

This might help you out:

http://www.cokeandcode.com/pathfinding

Answer 2

The book AI for Game Developers has a very good explanation of A*. I was actually going to write an implementation today... if I do I'll throw the code up here.

The code is done, it is too big to put here, so you can grab it from: https://chaos.bcit.ca/svn/public/astar/ (self signed certificate, but the server doesn't do anything evil).

I followed the pseudo-code in the book for the most part, but I made everything much more object oriented than anything I have seen thus far for A*.

You have a Maze that consists of Tiles. Each Tile has a Location and an Obstacle (null if there is no obstacle).

You can use a PathFinder (like AStar) to find th shortest path between a given start and end location. You get a Path back which includes the Tiles you need to go through to get from the start to the end.

You can change the heuristic calculation by providing a different HeuristicCalculator (the current one just checks to see if there is an Obstacle or not and figures out the shortest number of Tiles to go through, you could add weights to different Obstacles for instance if you don't like the default).

The code is license under the LGPL, so if you make changes and distribute the app you have to make the changes available. Feel free to send bug reports/fixes to the email address in the license comment (found in each header).

I'll get around to commenting it after exams, but I think it is pretty straight forward.

Answer 3

Naturally you will learn a lot about pathfinding if you write your own implementation. But you will also spend a lot of time doing it.

Check out the JGraphT library that deals with graphs in general, has a nice API and supports more shortest path algorithms than just A*.

Answer 4

This is the most informative Pathfinding post I've seen to date: http://www.ai-blog.net/archives/000152.html