   A* Implementation
  Hi.I've been looking up the A* algorithm for my roguelike, and I'm fairly confident I understand it.The issue I've been having is with actually implementing it.So far, I've typed up 50 lines or so and just deleted it after I feel it's completely useless - most of the time, I don't know what I actually typed (not copy-pasting, or copying). I feel it might be to do with how I'm *sorting* stuff out.The pathfinding function,  at the moment, takes in the start/end points, a pointer to the level, a reference to the list of points it fills, and a reference to a list of points explored (the way I'm trying to run it is that each monster knows where it has explored, and keeps track of this so it tries to avoid retracing steps; higher F cost for explored tiles).This seems a bit over the top. Also, in my function I then have a closed list, an open list, as well as a current path. (all std::list).I think I'm getting into somewhat of a mess. I've tried looking all over the interwebs, and cannot find anything that helps me with the implementation. The article here on GD.Net, IMO, is great in the theory, but has no impl. link. Can anyone help me with this?Thanks. :D-Mark.P.S. I'm not looking for code to copy-paste. I'm looking for some idea of a structure for my pathfinding function.   
  Odds are you're breaking A* by modifying the F cost for "previously explored tiles".  Don't confuse pathfinding with exploring.  They are 2 separate systems.  One decides where the AI wants to go (exploration), the other tells it how to get there (A* pathfinding).  Don't conflate pathfinding with your other systems.  That just means nothing will work.Implement a straight forward A*, not whatever complicated thing you're trying to do.  Simple A -> B pathfinding.  That's what A* does.  The A* wikipedia article has pseudo-code that's basically an implementation.To do exploration is a totally separate system: I've been to this room, so lets go to that room.  Nothing to do with pathfinding, per say.-me   ;  Oki.I'm not 'trying' to explore. I have the exploration bit pretty well down, I believe (If nothing interesting is in sight, pathfind to a random place).But I would probably have a situation, especially with my useless dungeon generation, where it would end up going back on itself. I don't think this would look very good.Instead, I'm trying to alter the G in F = G+H by if the square's explored, to take 'the path less travelled', as it were.Here's an example:The monster at the red dot going to the green dot. It could potentially take the line as a route. When it gets to the green point, it chooses the blue dot as a random point. It's very likely the monster would just retrace its steps, which would be unnatural.If I fiddle with the F cost for explored squares, the monster might take the leftmost corridor up, or even the route on the farleft of the map.And I shall check the wikipedia, thanks.On a side note, one bit that was getting me was my organization with the whole thing - do I need to pass in the list to fill, and pathfind once, or just return the next square?If I can just return the next square, is there a distance you can go with A* (or any other pathfinding, but greedy best thingy seems completely useless for my kind of map and dijstraka is not right either) when you can say 'stop computing, I know this route is right'?I'm sure CPU time won't be an issue - just fiddle with my blocking input to use spare time for potential pathfinding and thing.Thanks if you understood me.-Mark.   ;  Hey Commieduck,Have you constructed a set of nodes to travel on the map?I mean, you might have a map represented as vectors withwalls in it and such, but a good first step in implementing the A*is to map the points feasible to travel by.For instance, flood fill all the reachable parts first.(Your monster might not care (or know) for rooms out of reach)add nodes to the filled areas, and then perform the algorithm on those.-Or perhaps, i need more info. I guess if you understand A* correctly,it's just a matter of rewriting the code a little before you reacha fair implementation. Good Luck!   ;  SuperVGA:Um, I have my map as tile based, so (at least at the moment) I'm doing it as each tile is a node.What would the floodfill do? I can see it taking all reachable areas, but...or is that generating nodes?Thanks for the quick reply. :D-Mark.   ;  You're welcome :) Yes i think you should place ~equidistant nodes in the filledarea, and traverse with those instead. Really, the gif on wikipediaa-star algorithm page really can take it from there.It's sometimes good to abstract from "real" stuff in your program,such as the tile based map. This way, it's easier to interpret the worldin the context you need it in. As here, you really want to use a network of nodes. Later, you can shrink the distance between the generated nodes,and then finally, you'll see the way to treat every tile as a node. Right there.   ;  Hmm. I'm still not *entirely* sure how I would do equidistant points. I've got my map (actually, this is rough, but it's close enough to the actual format):The only way I can think of abstract points would be that every crossover-so room entrances, corridor crossings, etc. are a node. Then simply do bresenham's algorithm from node->random point.I'm not sure this is what you meant, can you elaborate?   ;  Back again, Commieduck.Yes, you could do it like that. That would be much better than whati first assumed you would do. Sounds quite reasonable.To have travelable space as the number of nodes to traverse is really much.You want to direct the monster at entrances to passageways to the target point.The rest of the room is not of interest.This is why i suggest you first using less nodes.The naive way i'd do it at first, would be to randomly select points in the flood-filled area, and check that it is at least "range" away from previous points.This may sound time consuming, but i don't think you need more than 50 pointsfor the shown map. Many of which can be recycled. Ok, these points are your nodes. These are the ones you traverse.They may not be placed optimally (at exits of passages, corners and such),but that can be dealt with later.Find a way to show the nodes on the tilemap. Then check that the algorithmworks as it should. (Here, you could also place the nodes manually, which in case of developer-created maps will give a good result. :D )Then you can begin wondering about optimizing the node placement.This is much more complex than the actual A* implementation, and could take upmuch more code.If you did a non-A* method combined with bresenham to make the monstermove between rooms, you could use A* on the single last room with the target tile in it. That would be rather simple.But that's just an idea. I'm thinking for the actual implementation,first make a few nodes to implement and test different scenarios on.NOTE: The bresenham algorithm may be a little overkill for straight corridors,and also if corridors were, at some point, to twist and turn a bit, therewill be need for new nodes at the corners, to do bresenham on, as cells onthe straight line might not be directly passable.   ;  Ok, I can see what you mean now. Thank you very much for your help, much appreciated. :DThat is a very early map; believe it's 94x53 characters, whereas my new map is 127*127 (3~ times bigger). So that means more nodes, and more searching.I would've said that some places you would need nodes-the corners of corridors, and when a corridor enters a room. I think this is going to give me more than enough nodes, even too many.I think there wouldn't be much point in taking the node->random point tiny little step. Anyway, rooms auto-explore when you enter, and this could make it easier for monsters.I think I have got more than ehough to have a play with.Thank you again. :D-Mark.   ;  You're very welcome. Feel free to PM the results if youdiscover something interesting. Or annoying for that matter. :P   