Im tossing around a few Ideas in my head on how to do collision detection/pathfinding. Let me know what you think of this idea, since it seems to be the least time/cpu consuming A binary file that describes the room the Ego is in (Ego being the main character) ie: It describes the bounding boxes of the room where the ego can and cannot walk, it would also have descriptions for the text (ie: certain events, items, general description of the area, et al.) Now, as far as path-finding is concerned.. Im not going to bother with that for a little bit, since Im thinking - loads and loads of invisible lines? - the ego is going to be controlled by the mouse, not by keyboard movement. --LordKaT

I did some work on this a couple of years (5?!!) back when me and some friends worked on an adventure game for fun. Needless to say it was huge and we never finished it. Anyway, back in those days, while I was still unspoiled by CS theories, we invented an algorithm which I will explain. If Dijkstras and A* finds the *shortest* path our just found the path....

Basically we let the path consist of a bunch of straight lines that are connected. Then we find the source and destination lines, if those are the same, we just let Ego move to the destination point on the line. Otherwise we let him move to one of the endpoints of the current line, the one that's closest (in coordinates) to the destination line and enter the next line. We repeat that until Ego has reached the destination point on the destination line.

This works pretty well as long as you:
a) let all lines be connected into a full path (this may seem bad if you for instance want to block entrance until a certain condition has been met, but that's easily circumstanced by not adding that line until that condition has been met)
b) don't use circular paths. However you might be able to tweak the algo to do just that, but we never got around to do that.

Obvious improvements are to put all lines of the path in a graph and do Dijkstras or A* to find the shortest path to the destination line. That way you will at least not get problem with circular paths. I recommend Dijkstras in this case, since it's easier to implement.
However it will be a bit backwards, since every line in the path will be a vertex in the graph and every endpoint of the lines will be an edge in the graph.
Hope this helps a bit.

Edited by - amag on March 30, 2001 11:18:21 AM