Before I lay out my problem I'll say two things, this is possibly more a general programming question but because it is so graph-search based I thought it appropriate to post here. The other thing is that I'm sure I'm either asking for something that can be solved either trivially simply and I'm just not seeing the obvious thing or it's as straight-forwardly computationally intensive as it sounds and I can't do it any faster. I've written a puzzle game where the player controls a character around a 17x18 grid. There are a variety of different tile types that affect the players movement and there are also other moveable objects (moved by the player bumping into them), collectables and switches to change the state of some tiles. The player can move North, South, East and West. I've written a level editor and I've included the ability for the level editor to check to see what the smallest number of moves through a level is. That was straightforward. The level is searched by Breadth First Search, each state the level could be in (position of player, position of objects, switch state, items collected) is a separate node. This runs nice and fast, even though I've implemented it in actionscript. I also want to include the ability to try and solve the level with a restriction on the players movement. That is I want to be able to say to the player (for example), "complete this level without moving North more than 5 times". So I want the level editor to be able to find the route of fewest moves that do not involve going *restricted direction* more than *x* times. Naively I implemented this functionality as a depth first search. The algorithm works fine in terms of correctness but, for any x over 5 (or even less for more complicated levels) I realise I could well be looking at heat death of the universe running time figures, or several hours at least. So I'm asking for some help on this, it seems to me what I want to do must surely be covered my some classic search algorithm or at the very least I should be able to augment the graph with information as I create it to greatly speed up the search when it is done. Could anyone offer any suggestions?.

It sounds like your game in its current state could contain Sokoban-like levels, and Sokoban can be a very difficult game to solve. Unless your game's interactions are much more limited, there's no way to ensure that your solver will run quickly.

What's wrong with including the moves taken so far in each node of the search? You then use that data to limit the possible successor moves at each step. Is it really any harder or slower than tracking the switch state or items collected?

Use the same search algorithm as without the restrictions. Keep track of the number of "north" moves(or whatever you are restricting) at each node in the search graph. If a move from a node goes beyond the restriction consider it an invalid move and don't add it to the search graph. If the game is possible with the given restrictions then this should reduce the number of moves necessary to be searched.

Quote:

Original post by Alrecenk Use the same search algorithm as without the restrictions. Keep track of the number of "north" moves(or whatever you are restricting) at each node in the search graph. If a move from a node goes beyond the restriction consider it an invalid move and don't add it to the search graph. If the game is possible with the given restrictions then this should reduce the number of moves necessary to be searched.

But given that my graph has multiple paths to the same node (and indeed full on cycles) I can visit a node that I have already visited but with fewer restricted moves on the new longer path. For example (if "north" is my restricted direction) I could have a path "nsewnes" to get to node but also "seweswenewswe" to get to the same node, from my point of view the second path is the better path as it has fewer restricted moves in it. I can't simply just update the node with the new number of restricted moves, I'd have to revisit every node visited from that node and update their restricted move count as well. That seems like an incredibly tricky (and potentially infinite looping) thing to keep track of.

I have had another idea to try and crack this problem.

I do a breadth first search with no restricted moves allowed. this gives me a visited subset of the graph. I then (for every visited node) follow the restricted move edge. Each node visited from this restricted move is put into a second set, obviously any already visited nodes are discarded. I then repeat the process (perform a breadth first search using all the nodes in the second set but without making any restricted moves then once complete make the restricted move from each visited node). I repeat this until I've done the maximum number of restricted moves. I'll have either visited a goal node or I won't.

Thanks for the comments, it's really helped my mind turn over the problem.

Consider the number of restricted moves a state of the level so that two nodes where everything else is the same will still be considered separate nodes if they have different values for the restricted item. Yes, it'll make your search graph bigger, but since the number of times this can happen is limited, and some nodes that might have existed before will be pruned because of the restriction it's not going to be too much slower. Actually, your last idea is very similar to what I was trying to suggest. I think it would work, and it would guarantee the least number of restricted moves. The way I was suggesting it would guarantee the least number of total moves if implemented correctly, and would be much easier to extend to a faster search algorithm, specifically A*. A* would return the same result as a breadth first search, but typically search a lot less nodes because it searches nodes that "look promising" first. It's a fairly simple algorithm and it's definitely something to look into if your searches are too slow.

I've just realised that while my approach will result in a route with the fewest possible restricted moves it will not necessarily find a route with the fewest possible overall moves while still obeying the restriction.

I need to 'personality' split my nodes as you suggest.

Or I could just feed the route produced from my technique into my depth first search alogrithm. The problem with the depth first search is that it struggles to find a complete route, once it has found the first complete route it uses it to limit it's search for further routes and swiftly finds the shortest

I think perhaps you're overcomplicating things, based on an imprecise definition of the problem. Remember, a 'node' in what you are searching is not a position in space or on the positional graph, but a tree of unique states. In many applications, each unique state corresponds directly to a unique position in space, but not in your application! Your application requires that not only is the position important, but the objects, switches, and previous moves are too. You should view it not as a pathfinding algorithm but as a planning algorithm, though the actual implementation is much the same, and will lend itself to DFS, BFS, or A* (if you can formulate an admissible heuristic).

So yeah, the main problem was really that I was quite a lot of an idiot, the final algorithm I'm using is a trivial tweaking of BFS. The main thing is I work backwards from the target node, using basically the algorithm I laid out.

I didn't need to do anything clever to revisit nodes when I discover a better route to a node, I was totally over-thinking it, I just need to semi-visit all nodes even if I have visited them before, to check if new route is better than old route. I suppose that with graphs with a couple of thousand nodes that could get slow but I think I'm good.

Thanks for the sounding board guys.