point 'n' click adventure pathfinding?
BlitzMax Forums/BlitzMax Beginners Area/point 'n' click adventure pathfinding?
| ||
| Has anyone here tried implementing the type of pathfinding that you used to find in adventure games such as Monkey Island or King's Quest? I've read about a number of different methods, but I'm looking for the simplest, easiest to implement way. Really any help/advice about this would be appreciated - ideas and techniques, code snippets, anything! |
| ||
| No ideas, anyone? |
| ||
| Have you seen the AStar Pathfinding Module? (link to wiki) |
| ||
| Hmm, thanks for the link but it looks grid-based to me. Am I wrong about this? |
| ||
| monkey island could as well be on such a grid.. not a flat square one, but a grid where each cell has an irregular shape.. In the end, pathfinding doesn't care what a mapunit/cell looks like, it only finds paths in a grid.. |
| ||
| Ok, I take your meaning and, conceptually, I understand it too. It doesn't help me make an actual working system though. I think the problem I'm having is that all the examples of A* that I've seen have been too general purpose, in possession of far too many confusing features that I don't need, and primarily grid based (often with disclaimers saying that they can be adapted to work in non-grid configurations, but skirting over how that might be done.) They also usually only feature eight degrees of movement, which is inadequate to reproduce the effect I'm looking for. What I need is more specific help to solve my particular problem; a simple, clean way to replicate the pathfinding found in typical old-school 2d adventure games without needless complexity or features that I don't need. Frankly I hate programming, and my mathematics is terrible, but I like creating, so the simpler the solution (and the explanation) the better! |
| ||
try a simple 2d grid then which is your room, and you simple walk from a to b by interpolating between these 2 points. To prevent walking through walls you could create a look-up for that grid. The lookup has, like, points moved away from walls.. uhm..
room:
. . . . . . . .
. . . . | . . . .
|
. . . . | . . . .
|
. . . . | . . . .
. . . . . . . .
lookup:
. . . . . . . .
. .
. . . | . . .
|
. . . | . . .
|
. . . . | . . . .
. .
. . . . . . . .
As you see I 'moved' the gridpoints a bit around the wall. No matter where you are in that grid, you can just walk to anywhere looking that look-up, the gridpoints force you to walk around the wall. Doesn't really work for very big 'n complex rooms with zillions of walls in all kinda shapes, but for simple stuff it might work.. |
| ||
| any method you use is going to use obstacle avoidance & pathfinding which require some math to perform. I would advise that if you are going to program (with Blitz or any language) that you really invest some time learning the Math. not a dig, just good advice. a good place to start is by taking a look at max's math mod. (sin,cos, atan, atan2, etc...) and Google for each one in turn and have fun with it. |
| ||
| Well since I only need to know this one particular thing, I think investing the significant amount of time it would take to study mathematics would be overkill, don't you? Besides, I have never and will never consider mathematics "fun" under any circumstances. :p I guess what I'm trying to say is that I'm using Blitz Max out of necessity rather than for fun, so I just want the quickest, easiest, most painless solution that won't sidetrack me for too long. |
| ||
| I understand what you are saying and I don't pretend to be a Math expert but from my experience, a crash course in Math (just a weekend) benefits every area of your programming. I am a more creative type. I enjoy modelling and photoshop over Math any day of the week. however :) , if you invest a small amount of time mastering a few Math fundamentals it will pay off huge. with that said. I will try to knock up some functions that may assist you. you want a non-player character to guide himself around a room avoiding collisions with objects while seeking a goal (doorway, object, whatever), right? |
| ||
| Yes, that's exactly it. Thanks! |
| ||
| AStar/A* is just the topic you'll have to do research. A* is nothing more than the rules of how to evaluate the next step from the current position, estimating it's costs and compare that to other moves to find the best path in the (hopefully) most efficient way. It doesn't matter if your examples are grid based, or if you have any kind of graph with connected nodes or how much connection went from a single node of if it's a different number of connections for different nodes - your typical evaluation loop just checks the given connections from the current node. I used such an approach in a Point&Click engine I wrote some years ago and it worked pretty well (we released a couple of games at the company I worked for back then). A more advanced solution would then not use single nodes but connected polygons/triangles but for a first step you should try to understand the basics using simple nodes (which might already be a reasonable solution for your game) Btw. A* needs almost no math besides addition and sqrt (for estimating the costs of a move/path) |
| ||
| I've done some testing with A* in a sample point-n-click adventure environment, and it does seem to be the best / most natural solution. Just a couple of thoughts: 1) It is grid based, but you can create a grid overlay for your walking map. Correspond the 'walkable' parts of the screen with values in an array for the A* searcher. 2) since there is a lot of calculations involved, you can greatly speed it up by using a lower resolution walk map than the actual screen resolution. E.g. have 1024x768 graphics, but use a 320x240 walk map. The downside is that your walking patterns are only up to 3 pixels accurate, but the time necesary to find a path is *much* smaller... making all the difference on a slow(ish) computer. Depending on how much accuracy you need, you can even use a 160x120 walkmap, if ~6 pixel accuracy is enough. (You can still walk on a pixel-by-pixel base, but your final target destination may be rounded a couple of pixels) What I did myself: Take a picture of the background. In a paint program, add a new layer and manually draw an overlay of the walkable bits in a very distinct color. When done, remove the real background, and save the image. I then loaded the new image in a small program I created, which would generate the walking map array based on the color of the pixels in the image. either it could take every x-th pixel to downsample the size of the walking map, or you could scale the image down in the graphics program in the first place and count every pixel after that. 3) Also important, figure out a way how to handle unreachable destinations. What I did myself if you click on a target destination for which there is no walkable path: figure out a straight line between the target and destination points. Then pick an alternate destination point that is 90% on that line. If there is a path possible, walk there instead. If it fails to, check at 80%, 70%, 50%, 40%, 25%, 15%.... You'll walk 'most' of the way, until blocked by something. Much more user friendly and natural than refusing to walk altogether if there is no direct path. Another tip: some A* routines only account for horizontal & vertical movements. You'll probably get more natural looking results if you also make diagonal movement possible, since in real live people would tend to take the direct route as well. Last but not least: if you have a background with much perspective (e.g. road leading into the distance, hills, etc) you probably also have to figure out a way to include some kind of dept map to account for the size of your character on various parts of the map. Have him/her get scaled small when far away, and full-size when up close. Possibly also slow down movement speed in pixels/sec when the sprite is far away (although not quite as much as in real life, or it will get tedious to wait for it to finish walking) |
| ||
| An alternative to nodes positioned on a grid is to use nodes only around obstacles and near incorners and outcorners and near passages (on both sides). Each node has one or several links to others nodes of the same zone (room), and instead of checking if the cells at front, at back, at left, at right, are accessible, you check which are the links from this node to others nodes and consider these others nodes as potential nodes for the path. This dramatically decreases the number of nodes required. When creating links between nodes, in 2d, you can probably use a kind of "2d linepick" : draw a line between node and other node on another image and check if one of the pixel of the line intersects with a pixel of an obstacle or of a wall, if yes, it means that the path is blocked, if no, it means that the path is free... |
| ||
| ...You do realize this was a 10 year old thread? :-) |
| ||
| RemiD The Thread NecroMancer ;-) ..but kidding aside, not locking up a thread is also a good thing because some forums have a date expiration on them, and so this allows newbies to ask or follow up a question related to that thread, particularly if some participants are still around after all these years. |
   |