If a game map is partitioned into subgraphs, how to minimize edges between subgraphs?
I have a problem, I'm 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 the number of vertices for each subgraph that acts as a soft constraint.
Alternatively, you could say I am looking to find bridges between subgraphs, but its generally the same problem.
Grid-based game map example
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.
A possible solution to the problem is the Kernighan Lin algorithm :
function Kernighan-Lin(G(V,E)): determine a balanced initial partition of the nodes into sets A and B do A1 := A; B1 := B compute D values for all a in A1 and b in B1 for (i := 1 to |V|/2) find a[i] from A1 and b[i] from B1, such that g[i] = D[a[i]] + D[b[i]] - 2*c[a][b] is maximal move a[i] to B1 and b[i] to A1 remove a[i] and b[i] from further consideration in this pass update D values for the elements of A1 = A1 / a[i] and B1 = B1 / b[i] end for find k which maximizes g_max, the sum of g,...,g[k] if (g_max > 0) then Exchange a,a,...,a[k] with b,b,...,b[k] until (g_max <= 0) return G(V,E)
My problem with this algorithm is its runtime at O(n^2 * lg(n)), I am thinking of limiting the nodes in A1 and B1 to the border of each subgraph to reduce the amount of work done.
I also don't understand the c[a][b] cost in the algorithm, if a and b do not have an edge between them is the cost assumed to be 0 or infinity, or should I create an edge based on some heuristic.
Do you know what c[a][b] is supposed to be when there is no edge between a and b? Do you think my problem is suitable to use a multilevel method? Why or why not? Do you have a good idea for how to reduce the work done with the Kernighan-lin algorithm for my problem?