search

mgerhardy / caveexpress

CaveExpress is a classic 2D platformer with physics-based gameplay and dozens of levels. CavePacker is a Sokoban game.
http://www.caveproductions.org/
Other
144 stars 20 forks source link

CAVEPACKER: Deadlock detection #24

Closed mgerhardy closed 8 years ago

mgerhardy commented 9 years ago

There are several deadlock situations in sokoban (find more about that here: http://www.sokobano.de/wiki/index.php?title=Deadlocks )

CavePacker should include a detection for some of them and report the deadlock to the player.

mgerhardy commented 9 years ago

0402dde99b4f972b67606ad809c0315c67014e35 428ea4748dca7514b62b5815dfc5edd0beb3b116

mgerhardy commented 9 years ago

frozen deadlock detection and blocked field deadlock detection is implemented. There are still a lot more - but let's see whether we can really do them in real time on mobile devices.

mgerhardy commented 9 years ago

I had to limit the frozen deadlock detector to use max 50ms per frame - after that is reached, we will abort the detection. The problem is that some maps have a very high amount of packages next to each other that would result in a huge amount of calculation for the frozen detection. Maybe I can optimize the algo by doing some smart caching.

mgerhardy commented 8 years ago

http://mgerhardy.blogspot.de/2015/12/sokoban-deadlock-detection-cavepacker.html