Well, Martian Madness has morphed into a sort of team based RTS and I’ve just started considering path finding. I have an free form map in which I can place obstacles… any one have any useful links/info on how to perform path finding between two points…
And yes… I’m just off to trawl google 
Kev
There’s also an A-star and i believa modified A-star that prefers interior paths (more natural looking)in Scroller.
But I’m not sure A-star is going to work for him if his map is truely free-form with no cellular structure at all.
Typically free-form environments are done with way-points.
I’m afraid I couldn’t gleen anything from the puppy games library AStar algorithm…
The map is fairly freeform there are screenshots here:
http://www.newdawnsoftware.com/martian/screenshots
Waypoints sounds like a lot of extra map design up front.
Kev
Hm., This is a horizontal scroller it looks like, Usually these don’t
require much pathfinding.
What exactly are you trying to accomplish?
Ah no, the later screenshots show what I’m trying to do now… its a kinda psuedo-isometric rts style game now…
EDIT: would have probably been easier if I’d just posted the screenshot direct in the first place… sorry about that: http://www.newdawnsoftware.com/martian/screenshots/241203_4.gif
Kev
I would think A-Star would be perfect for that kind of “map”.
From what I understand (not much) about A-Star its based on building of graph of nodes representing the possible locations on the map. After that its just simple graph theory (which I do get :)).
What I can’t understand is how you build a graph that represents a map where the locations arn’t grid based. Do you impose a grid onto the map to assist in building nodes and hence the graph?
Kev
That’s one possibility anyway - create a grid such that the smallest unit fits into a grid square. You can even make it coarser and still maintain the one-grid-to-one-unit mapping if you have larger variations in unit size. You just have to make sure that the unit go to the exact spot the player clicked on so the grid structure is not apparant to the him.
A* works with any topography. The nodes you create should represent the complete, discrete state at any one stage in the puzzle; and you must be able to provide a heuristic which guesses the cost of changing from one state to each of the possible adjacent states.
For a grid topology, the state can be very easily represented as a coordinate (x, y), and the adjacent states are likewise very easy to find, as they’re the set of 8 coordinates surrounding (x, y). Likewise the cost is generally very easy to computed, based on some arbitrary “difficulty” of traversing the map at that point. Some states won’t be possible because there’s a wall in that map grid. The goal state is simply a node with the desired x,y coordinate. The SPGL AStarInt algorithm is optimised for simple tile maps and 2D grids.
It starts getting more interesting when you stop representing the world as a grid. A state in 3D would most likely consist of an approximate coordinate in space (given by x, y, z, r for example). The surrounding states would be perhaps generated by casting rays from that point in different directions. The goal state would be to be within a certain range of a goal coordinate gx, gy, gz.
The cost of getting from x1,y1,z1 to x2,y2,z2 would be dependent on your physics model. Going down is always easier than going up when there’s gravity involved, so you might guess the cost of a route as being the distance in the 2D plane, plus a factor times the height if the height needs to be increased.
The SPGL algorithm is the basic A* algorithm. All the cleverness comes from your heuristics and choice of adjacent node states.
Cas 
Another simple dodge is to create a reasonably small grid such that grid squares are smaller then your objects. Then consider any grid square an object intersects with to be “filled”. It means that in some cases you may end up with some “elbow room” but if the grid box size == the maximal acceptable elbow room it aught to work.
OR jsut restrict object placement to the grid. Thats how virtually every isometric game works today and they look and play fine
Just wanted to pop back in and say thanks for the assistance, its working…
http://www.newdawnsoftware.com/martian/screenshots/301203_1.gif
Seems to pick some slightly odd routes now and again.
I’m currently using the “Manhattan” heuristic. Has anyone experimented with anything else and got good results?
Here’s the reference I used should anyone want it in the future, its pretty good for a useless newbie like me:
http://www.policyalmanac.org/games/aStarTutorial.htm
Kev
I’ve actually put it in the game now and there are slight slow downs while the paths are found. Do I just need to keep trying to optimize the search routine or is threading likely to help?
Kev
I’m getting some pretty terrible times for searched relatively short paths with a good accuracy.
I guess I need to add waypoints in addition to the A* search paths?
Kev
The A* algorithm is very cunningly designed so it can be run one step at a time.
Rather than run it in a thread and risk it being run spuriously you need to timeslice it in your “thinking” thread, and run a specific number of steps at a time. While it’s running the gidrahs don’t move of course but that’s all you can hope for. Or you can simply start them moving in the best direction yet found and correct it as the algorithm homes in on the best answer. Which is very like how people solve the same problem.
Cas
Waypoints can make all the difference. Using multiple pathfinding techniques will almost certainly get you both the most accurate and fastest possible path.
For instance, you can have way points that connect all “rooms” together and use something like Dijkstra’s (sp) algorithm to search between them. Then you can use a 2d array to build a table of the fastest way between these points. This table would be generated when the level is generated and saved as part of it. I can explain this in more detail if you are interested. I have a sample Flash app I wrote that illustrates this too. I can dig it up if you want it (it was just a prototype, so don’t expect much ;)).
To handle pathfinding within a room, you would still use A* but for cross-room pathfinding, you could use the way points. Using the two of these together can give you some fast and natural looking paths.
The problem then is handling collisions with other characters. A* is really good at a changing environment and way points are not unless you re-calculate paths between them when things change.
There are several articles about mixing algorithms in the Game Developer Gems books by Charles River (I own every one of those books and recomend them to everyone interested in this stuff). Don’t miss the AI Game Wisdom book either. If you need the specific article, let me know and I can tell you the book and chapter title.
For some other interesting reading in those books, hit the articles by the BioWare guys about “depth of field/area of concern” stuff and the Ensable Studio guys about determining threats and LoS on a tile-based map.
Mike
mike@electrotank.com
[edit: fixed a typo + made last paragraph more clear ]
Well, thanks for the post! (you almost rival blahblahblah for scale of posts ;)). I’ve decided to not worry about it for a while, although I’ve added waypoints for the maps. Not really far enough long to be getting bogged down.
As to the entity/entity collision, I was considering allowing the entity to discover this on the fly and move “around” the blocking entity.
For my future reference, and others if they’re reading this… where might we find the BioWare articles?
Kev
EDIT: Incidently, I found DJK much easier to understand and implement than A*. Strange how minds work isn’t it?
Yeah, I’ll try to keep em shorter from now on
I edited the last post to make it more clear. The articles I was refering to in the last paragraph are in those Game Dev Gems books or AI Game Wisdom. I can find the specific details if you are so inclined. Thanks!
Mike
I think we should get Adam to post using MIME encoded zipped text to save on our bandwidth
Cas
