I''ve looked into lots of algorithms, including A* - but nothing seems sufficient for 2d point''n''click adventure games. The only thing I can think of which would work is the SCUMM (Monkey Island, Zak McKracken) method of pathfinding boxes. This is how it works, in theory To find the shortest path from one point to another, we split the screen into boxes. Even though they''re called boxes, they can form the shapes of triangles or trapeziums. The boxes are drawn for hand in an editor. Structure of a box: (XTL) ___________ (XTR) XTL (Top Left corner) / (YT) \ YT (Top line) / \ XTR (Top Right corner) / \ XBL (Bottom Left corner) / \ YB (Bottom line) (XBL)/ (XB) \(XBR) XBR (Bottom Right corner) ~~~~~~~~~~~~~~~~~~~~~ The boxes are defined so that if box that should be connected to another, there must be an intersection. ____ ___ _____________ ______________ / | / | | | | | / | / | | |_________| | / |/ | | 1 X 2 Y 3 | ~~~~~~~X~~~~~~~ | |~~~~~~~~~|______________| ~~~~~~~~~~~~~~~ X marks the spot In the case of example two (3 boxes - 1, 2 and 3), box number 2 is connected with box number 1 and 3 not only with a single point, but two points, which form a line, or distance. The intersection (or destination if you like) is the middle of that line. To move from a point in box 1 to a point in box 2 we will need to follow a straight line to the intersection, marked X (the middle of box2''s YT/YB). Once we reach the intersection, we are now in box 2 and then just go to the destination point. BOX MATRIX The box matrix tells the interpreter how to make an actor walk between boxes. For example, if two boxes are reasonably close, but there is a fence in the way that should prevent them from walking that way, then the actor needs to walk around the fence when the box on the other side of the fence is clicked on. The left side of the matrix is the ''from'' box and the top of the matrix is the ''to'' box. For example, To +-------------+ | 0 1 2 3 | +---+-------------+ F | 0 | 00 01 01 01 | r | 1 | 00 01 02 02 | o | 2 | 01 01 02 03 | m | 3 | 02 02 02 03 | +---+-------------+ To walk from box 3 to box 0, you have to firstly walk through box 2. To then walk from box 2 to box 0, you have to walk through box 1, and finally to walk from box 1 to box 0, you simply have to walk straight to box 0. Now, matrices of the pattern above are for rooms that have there boxes nicely joined in a row like so: +------+ +------------+ +------+ +------+ | | 0 | 1 | 2 | 3 | +------+------+------+------------+ However, a lot of rooms have a fairly complex walking space which gives rise to larger matrices with more complex patterns. +--------+ | 4 | +-+----+-+ +-------+ | 2 | +-----------+ | 0 +---+----+---+ 3 | | | 1 | | +-------+------------+-----------+ For example, the layout shown above would produce a matrix as follows: 00 01 01 01 01 00 01 02 03 02 01 01 02 01 04 01 01 01 03 01 02 02 02 02 04 The data above would be stored in a file as: 00 01 01 01 01 00 01 02 03 02 01 01 02 01 04 01 01 01 03 01 02 02 02 02 04 THE ACTUAL USAGE Pathfinding process: 0. get destination point x,y on screen. 1. if destpoint is inside a box, determine which one. 2. if destpoint is outside any box, determine the closest box to that point. 3. if current box is the DestBox, go to dest point or nearest (if outside) then finish. 4. if not in the destbox, lookup in the matrix to find NextBox in order to reach DestBox. 5. go in a straight line to NextBox''s intersection point, then go to 3. ----------------------------------------------------------------- Now, this would look fine to me... if I had a brain! PROBLEMS: 0.9 Determine if a point is inside a box. How ? 2. How to calculate the Box Matrix in a walkbox editor ? Solutions welcome. This one''s been bugging me for ages! In other words.. How the heck do I implement this ? Thanks, Lloyd

I am wondering. this site is full of several hints for anything,
but it is difficult to find something concerning classic
2D Adventure engines. Nobody is making this kind of games?
do you know a site, which is concerned with this style of games?


krompo