how to solve theta mazes using opencv python?

Question

I have to find shortest path from the center of the maze to the outermost circle. I have to solve this problem using opencv and python

Rimester

Good luck with it. – Sheryllshetland

Answer 1

I'm out!

You can consider every white pixel in the image as a node of an undirected weighted graph. Every pixel (node) is connected to it's white neighbours. The weight of the edge connecting the two nodes is 1 in horizontal and vertical direction, and sqrt(2) (or simply 1.414) in diagonal direction.

Than, since you know starting and ending point, you can run Dijkstra algorithm to find the shortest path between start and end.

I used Rosetta Code implementation of the Dijkstra algorithm:

This is the code (not really polished, but working). The code is in C++, but should be easily convertible to Python, specially if you can find a good implementation of the Dijkstra algorithm:

#include <opencv2/opencv.hpp>


#include <iostream>
#include <vector>
#include <string>
#include <list>

#include <limits> // for numeric_limits

#include <vector>
#include <set>
#include <utility> // for pair
#include <algorithm>
#include <iterator>

using namespace cv;
using namespace std;

typedef int vertex_t;
typedef double weight_t;

const weight_t max_weight = std::numeric_limits<double>::infinity();

struct neighbor {
    vertex_t target;
    weight_t weight;
    neighbor(vertex_t arg_target, weight_t arg_weight)
        : target(arg_target), weight(arg_weight) { }

    bool operator == (const neighbor& other) const {
        return target == other.target;
    }
};

typedef std::vector<std::vector<neighbor> > adjacency_list_t;


void DijkstraComputePaths(vertex_t source,
    const adjacency_list_t &adjacency_list,
    std::vector<weight_t> &min_distance,
    std::vector<vertex_t> &previous)
{
    int n = adjacency_list.size();
    min_distance.clear();
    min_distance.resize(n, max_weight);
    min_distance[source] = 0;
    previous.clear();
    previous.resize(n, -1);
    std::set<std::pair<weight_t, vertex_t> > vertex_queue;
    vertex_queue.insert(std::make_pair(min_distance[source], source));

    while (!vertex_queue.empty())
    {
        weight_t dist = vertex_queue.begin()->first;
        vertex_t u = vertex_queue.begin()->second;
        vertex_queue.erase(vertex_queue.begin());

        // Visit each edge exiting u
        const std::vector<neighbor> &neighbors = adjacency_list[u];
        for (std::vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();
            neighbor_iter != neighbors.end();
            neighbor_iter++)
        {
            vertex_t v = neighbor_iter->target;
            weight_t weight = neighbor_iter->weight;
            weight_t distance_through_u = dist + weight;
            if (distance_through_u < min_distance[v]) {
                vertex_queue.erase(std::make_pair(min_distance[v], v));

                min_distance[v] = distance_through_u;
                previous[v] = u;
                vertex_queue.insert(std::make_pair(min_distance[v], v));

            }

        }
    }
}


std::list<vertex_t> DijkstraGetShortestPathTo(
    vertex_t vertex, const std::vector<vertex_t> &previous)
{
    std::list<vertex_t> path;
    for (; vertex != -1; vertex = previous[vertex])
        path.push_front(vertex);
    return path;
}

struct lessPoints
{
    bool operator() (const Point& lhs, const Point& rhs) const {
        return (lhs.x != rhs.x) ? (lhs.x < rhs.x) : (lhs.y < rhs.y);
    }
};

int main()
{
    Mat1b img = imread("path_to_image", IMREAD_GRAYSCALE);
    resize(img, img, Size(), 0.5, 0.5);

    copyMakeBorder(img, img, 1, 1, 1, 1, BORDER_CONSTANT, Scalar(0));

    Point startPt(150, 150);
    Point endPt(160, 10);

    Mat1b mask = img > 200;

    vector<Point> pts;
    findNonZero(mask, pts);


    map<Point, int, lessPoints> mp;
    for (size_t i = 0; i < pts.size(); ++i) {
        mp[pts[i]] = i;
    }

    adjacency_list_t adj(pts.size());
    for (size_t i = 0; i < pts.size(); ++i) {

        int r = pts[i].y;
        int c = pts[i].x;

        // TODO: Check valid range

        if (mask(r - 1, c - 1)) { // Top Left
            adj[i].push_back(neighbor(mp[Point(c - 1, r - 1)], 1.414));
        }
        if (mask(r - 1, c)) { // Top 
            adj[i].push_back(neighbor(mp[Point(c, r - 1)], 1.0));
        }
        if (mask(r - 1, c + 1)) { // Top Right
            adj[i].push_back(neighbor(mp[Point(c + 1, r - 1)], 1.414));
        }
        if (mask(r, c - 1)) { // Left
            adj[i].push_back(neighbor(mp[Point(c - 1, r)], 1.0));
        }
        if (mask(r, c + 1)) { // Right
            adj[i].push_back(neighbor(mp[Point(c + 1, r)], 1.0));
        }
        if (mask(r + 1, c - 1)) { // Bottom Left
            adj[i].push_back(neighbor(mp[Point(c - 1, r + 1)], 1.414));
        }
        if (mask(r + 1, c)) { // Bottom
            adj[i].push_back(neighbor(mp[Point(c, r + 1)], 1.0));
        }
        if (mask(r + 1, c + 1)) { // Bottom Right
            adj[i].push_back(neighbor(mp[Point(c + 1, r + 1)], 1.414));
        }
    }


    vertex_t start_vertex = mp[startPt];
    vertex_t end_vertex = mp[endPt];

    std::vector<weight_t> min_distance;
    std::vector<vertex_t> previous;
    DijkstraComputePaths(start_vertex, adj, min_distance, previous);

    Mat3b dbg;
    cvtColor(mask, dbg, COLOR_GRAY2BGR);
    circle(dbg, startPt, 3, Scalar(0, 255, 0));
    circle(dbg, endPt, 3, Scalar(0, 0, 255));

    std::list<vertex_t> path = DijkstraGetShortestPathTo(end_vertex, previous);

    for (vertex_t v : path) {
        dbg(pts[int(v)]) = Vec3b(255, 0, 0);
        int vgfd = 0;
    }

    imshow("Solution", dbg);
    waitKey();

    return 0;
}

Blue

Answer 2

You can use skimage.graph to implement it easily.

import skimage.graph
### give start (y1,x1) and end (y2,x2) and the binary maze image as input
def shortest_path(start,end,binary):
    costs=np.where(binary,1,1000)
    path, cost = skimage.graph.route_through_array(
        costs, start=start, end=end, fully_connected=True)
    return path,cost

Modred