3d Point'n'click (ie. Sam and Max) pathfinding?

Blitz3D Forums/Blitz3D Programming/3d Point'n'click (ie. Sam and Max) pathfinding?

JustLuke (Posted 2008) [#1]

I've no idea how to even begin to implement similar pathfinding to that found in Telltale's Sam and Max episodic games. I'd like to. Complex pathfinding algorithms seem like overkill. Any ideas of how I might go about doing this? The simpler the solution, the better!

Ross C (Posted 2008) [#2]

Do you mean a* pathfinding? There are some decent libs lying about for that, or do you mean something even more complicated? You could have waypoints instead (Basically pivots). You place the waypoints at junctions in the scene, and have the player walk towards them, and do a very quick distance calculation and find the quickest path. A slightly simplified version of the grid based pathfinding. Works best with less waypoints i feel.

chwaga (Posted 2008) [#3]

I think what you want is A*, 2D pathfinding.

Kryzon (Posted 2008) [#4]

Or adapt the A* into a waypoint net-like scheme. Use the A* but instead using the waypoint nodes as the slots to compute the path (as opposed to a full grid of blocked and walkable slots).

xlsior (Posted 2008) [#5]

I've played around with this a bit in the past, and found the following to work fairly well: 1) Make a 2D map of the 'walkable' parts of the map, drawn on top of the real background picture 2) Scale down the map to 1/4 or 1/8 of the actual resolution (or however little accuracy you can put up with) -- this means a significantly smaller map to parse, and therefore much less overhead finding an optimal path 3) Store the 2D map in an array 4) Run the a* against the array something else to think about, is what to do when you click on a part of the map that is unreachable. Here's what I did: If you determine the destination to be unreachable, calculate a direct line between the source and destination point. Starting at the destination point, do an A* back to the starting point. If it fails, move 32 pixels (or something) closer to the start on the line and calculate again. Repeat until you get a solution. When you have a solution, let your character walk this path in reverse -- essentially this will make him walk towards your desired destination point, but stop at the edge of the walkable area, where he'll be blocked. Looks much better than refusing to walk at all if there is no full path available. You can blend walking maps with waypoints as well, to easily add/remove barriers programmatically. For example, you have to cross a specific waypoint to walk across a drawbridge. You can disable the waypoint when the bridge is open, and re-enable it again when closed.