Translation of https://rosettacode.org/wiki/A*_search_algorithm (C++ variant) to D

astar.d

import std.algorithm.searching : find;
import std.container : DList;
import std.format : format;
import std.range :take;
import std.stdio;

class Point {
public:
    int x, y;

    this(int a = 0, int b = 0) {
        x = a;
        y = b;
    }

    override bool opEquals(const Object o) {
        Point rhs = cast(Point) o;
        return rhs.x == x && rhs.y == y;
    }

    Point opBinary(string op)(const Point o) {
        static if (op == "+") {
            return new Point(o.x + x, o.y + y);
        }
    }

    override string toString() const {
        return format("(%d, %d)", x, y);
    }

    int calcDist(Point p) {
        // need a better heuristic
        int dx = this.x - p.x;
        int dy = this.y - p.y;
        return (dx * dx + dy * dy);
    }
}

class Map {
public:
    char[8][8] m;
    int w, h;

    this() {
        char[8][8] t = [
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 1, 1, 0],
            [0, 0, 1, 0, 0, 0, 1, 0],
            [0, 0, 1, 0, 0, 0, 1, 0],
            [0, 0, 1, 1, 1, 1, 1, 0],
            [0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0]
        ];
        w = h = 8;
        for (int r; r < h; r++) {
            for (int s; s < w; s++) {
                m[s][r] = t[r][s];
            }
        }
    }

    int opIndex(int x, int y) {
        return m[x][y];
    }
}

class Node {
public:
    Point pos, parent;
    int dist, cost;

    this(Point pos, int dist=0, int cost=0, Point parent=null) {
        this.pos = pos;
        this.dist = dist;
        this.cost = cost,
        this.parent = parent;
    }

    override bool opEquals(const Object o) {
        return pos == (cast(Node)o).pos;
    }
}

class aStar {
private:
    Point[8] directions = [
        new Point(-1, -1),
        new Point( 1, -1),
        new Point(-1,  1),
        new Point( 1,  1),
        new Point( 0, -1),
        new Point(-1,  0),
        new Point( 0,  1),
        new Point( 1,  0)
    ];
public:
    Map map;
    Point end, start;
    DList!Node open;
    DList!Node closed;

    this() {
        closed = DList!Node();
        open = DList!Node();
    }

    bool isValid(Point p) {
        return (p.x > -1 && p.y > -1 && p.x < map.w && p.y < map.h);
    }

    bool existPoint(Point p, int cost) {
        auto i = closed[].find!((a, b) => a.pos == b)(p);
        if (!i.empty) {
            if (i.front.cost + i.front.dist < cost) {
                return true;
            } else {
                closed.linearRemove(i.take(1));
                return false;
            }
        }

        i = open[].find!((a, b) => a.pos == b)(p);
        if (!i.empty) {
            if (i.front.cost + i.front.dist < cost) {
                return true;
            } else {
                open.linearRemove(i.take(1));
                return false;
            }
        }
        return false;
    }

    bool fillOpen(Node n) {
        foreach (direction; directions) {
            // one can make diagonals have different cost
            int stepCost = (! direction.x + direction.y % 2) ? 1 : 1;

            Point neighbour = n.pos + direction;
            if (neighbour == end) {
                return true;
            }

            if (isValid(neighbour) && map[neighbour.x, neighbour.y] != 1) {
                int nc = stepCost + n.cost;
                int dist = end.calcDist(neighbour);
                if (!existPoint(neighbour, nc + dist)) {
                    Node m = new Node(neighbour, dist, nc, n.pos);
                    open.insert(m);
                }
            }
        }
        return false;
    }

    bool search(Point s, Point e, Map map) {
        this.end = e;
        this.start = s;
        this.map = map;

        Node n = new Node(s);
        open.insert(n);

        while (!open.empty) {
            Node front = open.front;
            open.removeFront();
            closed.insert(front);

            if (fillOpen(front))
                return true;
        }

        return false;
    }

    int path(DList!Point* path) {
        path.insertFront(end);
        int cost = 1 + closed.back.cost;
        path.insertFront(closed.back.pos);
        Point parent = closed.back.parent;

        foreach_reverse (n; closed) {
            if (n.pos == parent && n.pos != start) {
                path.insertFront(n.pos);
                parent = n.parent;
            }
        }
        path.insertFront(start);

        return cost;
    }
}

int main(string[] argv) {
    Map map = new Map();
    Point start = new Point();
    Point end = new Point(7, 7);
    aStar as = new aStar();

    if (as.search(start, end, map)) {
        auto path = DList!Point();
        int c = as.path(&path);
        for (int y = -1; y < 9; y++) {
            for (int x = -1; x < 9; x++) {
                if (x < 0 || y < 0 || x > 7 || y > 7 || map[x, y] == 1)
                    write(dchar(0x2593));
                else {
                    Point p = new Point(x, y);
                    if (!(path[].find(p).empty))
                        write("x");
                    else
                        write(".");
                }
            }
            writeln();
        }

        writef("\nPath cost %d: ", c);
        foreach (point; path) {
            writef("%s ", point);
        }
    }
    writeln();

    return 0;
}