Pathfinding in AHOG game
Community Forums/General Help/Pathfinding in AHOG game
| ||
| Hi again, I really have to implement a hint system in my adventure hidden object game. If you are not familiar with it, what this means: 1. the player is somewhere in the game in a random scene and have no idea what to do next 2. he is pressing the Hint button 3. based on a path, the game must show him where to go next. the idea is not to tell him: "go to the bedroom 2". i must guide him from scene to scene using some arrows. i never worked with path finding algorithms so what should I use? any easy to learn/understand mechanic? thanks, |
| ||
| I wouldn't think you'd need pathfinding per se, for that. What I would do is have an index for each room. Within that index, is the initial step you need to take to get to "bedroom 2". So, let's say you're in the conservatory. The index for the conservatory says to get to bedroom 2, you need to exit the screen at the left side. This step takes you into the kitchen. In the kitchen, the index says that to get to Bedroom two, the initial step you need to take is exit screen top - to go to the hallway. In the hallway, top click again, upstairs to the landing. From the landing, exit screen right to Bedroom 2. You would of course have to build the indices manually but I would think that's fairly trivial. |
| ||
| Hi GFK, I have like 84 scenes in the game. More than half are sometimes during the game... 'a hint target room'. Using your system, I have to put in every hotspot from ALL my 84 scenes paths to the other rooms... pretty trivial indeed. |
| ||
| Well, it might be a lot. But I don't think there's any other way, given that your locations don't exist in any structured form, which rules out any regular pathfinding technique you might have been able to use. I still think the indices method is the way to go, and I can't think of any way of automating the setup just now. Unless there was some way you could make a hidden "2d" version of your game world (a bunch of nodes, with a pre-calculated distance between each), and based the path finding off of that somehow. |
| ||
| It depends on a few things. Are the exits for each scene always just at the edges i.e. top,down,left and right? If you laid all the scenes down flat on a 2D grid and would that placement represent the true physical structure of the whole game world? If you can satisfy the above then you could automate pathfinding for each scene. If not then all you have are lots of unconnected locations which don't exist in any structured form e.g. a grid or as 2d or 3d points in a world and as such it's not possible to automate pathfinding without hard coding some extra information into each scene first. |
| ||
| Hello. There may be several ways to do what you want. I deduced the following: Your level is a network of rooms. Since you can have a room leading to several other rooms (not only through common doors, but secret passages etc.), we cannot use a 2D or 3D grid to represent this network (and thus we cannot use the A* algorithm, which takes physical distance between nodes as a measurement of the cost of travel). Therefore, just imagine an abstract network of linked nodes. Each node in this network is a room, and each node has links that connect this node to the other nodes it can lead to. Each link represents a portal (a door, a passage etc.) in your game through which the player travels between rooms. - - - - - There's some preprocessing required: 1) You need to identify and collect all 'terminating nodes'. These are nodes that only have ONE link, so they are at the "tips" of branches. 2) After having identified all terminating nodes, go through each terminating node and start building 'sections'. To do this, you begin at a terminating node and start travelling its single link, adding and NUMBERING the nodes you encounter on your way. For numbering, the first terminating node has the lowest index, 'zero', and the last node you encounter (another terminating node, which is the other end of the section) will have the highest index for this section. Each node with more than TWO links you encounter while building a section indicates a branch, and thus a new section needs to be created - if while building a section you reach a node with three links, for example, you build an extra section structure, populate it with the nodes that were previously travelled, then travel one link until you find an end (the first section), and then get back and travel the other link until you find the other end (the second section). Nodes with two links are normal intermediary nodes, since they come from a node and go to another node (two links). It's nodes with more than two links that indicate a branching. To recognize the ends of sections, you either reach another terminating node or you reach a REPEATED node (in the case of cyclic sections which loop). For these cyclic sections, the other terminating node of it is the node that precedes a repeated node - when you head into a repeated node (one that was already added and indexed in the section), consider the previous node the terminating node of that section. This is an artifical terminating node, it isn't included in the official terminating nodes list - it only exists for the section that has it. So each terminating node can belong to several sections. You can delete a section when you find that its pair of terminating nodes was already used by a section previously calculated - this means the sections would be the same, just the indexing that would be reversed. - - - - - Now for the pathfinding. Everytime the player selects that "Hint" you do: 1) Get the node for the room you're in, and also get the node for the relevant room you want to travel to (each room is associated with a node, so this is just querying a Field in your Room Type). 2) Go through ALL the sections you precalculated before, and collect the ones that have both your current node, and the relevant room node. If you have multiple occurrences (that is, multiple ways to arrive at the same relevant room), pick the occurrence that has the lowest DIFFERENCE between the indexes of the original node and the relevant node (this is the shortest way of all). 3) Reckon, based on the indexing of the section you picked, which direction to travel by. If your current node has a bigger index than the relevant room's node's index, travel in a negative direction (that is, head to the node one index lower than your current and repeat). If your current node has an smaller index than the relevant room's node's index, travel in a positive direction (head to the node one index above your current one, and repeat). When I say "travel", I mean indicate by an arrow the portal object in the room that you player needs to click or interact with to go to the room that the next node represents. This will eventually have you arriving at the relevant room. |
| ||
| Here are some images to illustrate the process. First you have the network of nodes for your level, each node representing a room:  Then you can identify the terminating nodes of this network: the ones with only one link.  Then you proceed to build sections. Since there are only two terminating nodes in this network, either one will cover all the sections - if there were more terminating nodes the amount of sections would increase exponentially. Each branch indicates new sections that need to be created. A network like this can have several paths, especially because of that cyclic element beginning at node 2. The following is a representation of how the algorithm works.  And then you use these sections for pathfinding like explained in part 2 of the previous post. |
| ||
| Take a look at graph algorithms. these are exactly what you're looking for. there's a ton of code floating around the web for breadth and depth first searches on graphs. the principle for you would be that your rooms act as nodes in the graph, and the graph edges would represent those rooms that are connected to each other. Once you've set this up, running a common search algorithm like a breadth or depth first search (or both, seeing a i guess you won't need to do it more than once really) which will give you the path to the room you need. If you gave each room on your game map a coordinate, you could write a little routine that set up the graph's connecting edges for you. easy! Cheers Charlie |
| ||
| If each room is connected to at least another room, and if you want to calculate the shortest open path from one room to another room, you can use the Astar algorithm with non grid nodes. However if you want the player to follow a specific path from one room to another but not necessarily the shortest path, you will have to define it manually... If you want to calculate the shortest open path from one room to another room : If you have a 2d or 3d representation of the rooms in a 2d or 3d space, you can automatically calculate the distance of each link from one passage to another passage. If you don't have a 2d or 3d representation of the rooms in a 2d or 3d space, you can manually attribute the distance or the "cost" of each link from one passage to another passage. Then you can use the Astar logic to automatically calculate the shortest and open path from one room to another. It is also important to store the state of each passage (open or blocked) so that you can take a passage into account or not when you use the path calculation routine. |
| ||
| again, this is out of my league.. i started Friday night to implement something similar. worked hard until now and have to test it. i hope it will work |
   |