0

I want to ask if there are easier step by step to make the path and possible solution for a game like this

  • I've already search pathfinding algorithm like A* and Djikstra.
  • I have read the article.
  • But, I don't really understand how to implement in a game like in the link above.
  • Please help if you know something about this. Thanks.
  • The language that i used is AS3 (actionscript-3).
Andri Wu
  • 105
  • 1
  • 2
  • 11
  • that game link froze mine opera :( so hard to say but if it is like Mah-Jong and You want to generate the tales so there is valid solution then just add random pair on random free top position until pyramid is form. To solve the game you have to do it brute force which is very slow :( may be some heuristics will help but not much. just solve it like you would and when you hit the wrong end back-trace to previous state ... and start again until valid solution found but the runtime will be horrible – Spektre Aug 12 '14 at 07:22
  • @Spektre Thanks for the reply. But the paths are complex. Because one tile can move to another tile if less than or equal two corners. Once I matched one pair, the path will change. Sorry if you can't open the link but the game name is dream love link 2. Try it from zibbo.com and search the dream love link 2. Can you give me some codes or source that will be understand easily in as3. Thanks a lot. – Andri Wu Aug 12 '14 at 07:49
  • 1. I do not have time to download and play/analyze game :) 2. as3 is unknown to me I code mostly in old C++ so source code is hard to give you should start coding on your own and when hit some wall post it here with exact problem specification. Btw if it is like mahjong why do you need path finding? – Spektre Aug 12 '14 at 07:58
  • You should start with the game data how the whole game is represented: the map of the board, tiles types and count (enum?) and so on ... Mahjong safe moves are when you have all 4 tiles accessible take them first (this move will never invalidate result) also when you have just one choise ... remember states only before you hit the first unsafe move ... this will speed up a lot the solving – Spektre Aug 12 '14 at 08:02
  • ah so You want the path for tile movement animation look here: http://stackoverflow.com/a/23779490/2521214 just load the map with walls (for tiles higher then the two matching) – Spektre Aug 13 '14 at 06:03

1 Answers1

0

I would do it like that:
1)Let's use backtracking with some heuristics(I don't know how fast it would actually work).

2)Let's assume that the the current state is S(state is defined by the tiles which are left).
If no tiles are left, the solution is found.

Otherwise, you can use, let's say, depth first search to find the pairs of matching tiles. A naive solution would be to try to match every pair, remove it and keep searching(and do backtracking if this branch fails).
However, there are a few heuristic to speed up the search:
a)If there are only two tiles of one type and they can be removed, remove them. Do not try to remove any other pairs in this state. I claim that if solution exists, it can obtained by removing this pair first.
b)If all tiles of one type can be matched now(even if there are more than 2 of them), match them. Do not try to remove any other pairs in this state.
c)If neither a) nor b) applies, then you will have to try all possibilities(like in a naive version).

As you can see, these heuristics allow you to avoid branching if either a) or b) applies to the current state, so they can speed up the search(especially at the end of the game, when only a few tiles are left and almost all of them are connected).

P.S You can also use memoization to avoid visiting the same state twice.

kraskevich
  • 18,368
  • 4
  • 33
  • 45
  • I do not think memoization will be a good idea unless some state compression is present because it would need really huge amound of memory just imagine the number of branch possibilities and now imagine their combinations and multiply it by state size (either sequence of moves or the tile-map) and you will be out of memory sooner then you think :(. The basic Idea is fine just on branching moves use state incrementing through all valid moves which allows to have singular instance of state for this. Example is here: http://stackoverflow.com/a/25203833/2521214 – Spektre Aug 13 '14 at 05:58
  • @Spektre The state is defined by the tiles which are left. It can be stored as a bitmask in one 64-bit(or maybe even 32-bit for maps with smaller number of tiles) integer. – kraskevich Aug 13 '14 at 06:59
  • in such coding it should be possible but beware that amount of processing needed to handle such state can cause extreme slowdowns of the solving runtime (such solver is ~O(m^n) where n is the number of brunches and m are average move possibilities). like for that example above (cube) complicated state was solving time around 238 hours and after simplification just ~11seconds (and n was just under 20 in mahjong it is many many more) – Spektre Aug 13 '14 at 09:45
  • @user2040251 Thanks for the reply. Can you give me some example of backtracking codes with heuristics. How can i generate the board tiles so they have their own path? Because each tile has different path. I'm sorry if i asked too many questions. – Andri Wu Aug 14 '14 at 02:32