How to find minimum cut-sets for several subgraphs of a graph of degrees 2 to 4
- by Tore
I have a problem, Im trying to make A* searches through a grid based game like pacman or sokoban, but i need to find "enclosures". What do i mean by enclosures? subgraphs with as few cut edges as possible given a maximum size and minimum size for number of vertices that act as soft constraints. Alternatively you could say i am looking to find bridges between subgraphs, but its generally the same problem.
Given a game that looks like this, what i want to do is find enclosures so that i can properly find entrances to them and thus get a good heuristic for reaching vertices inside these enclosures.
So what i want is to find these colored regions on any given map.
The reason for me bothering to do this and not just staying content with the performance of a simple manhattan distance heuristic is that an enclosure heuristic can give more optimal results and i would not have to actually do the A* to get some proper distance calculations and also for later adding competitive blocking of opponents within these enclosures when playing sokoban type games. Also the enclosure heuristic can be used for a minimax approach to finding goal vertices more properly.
Do you know of a good algorithm for solving this problem or have any suggestions in things i should explore?
