PathfindingSearch/DFID.java at main · itamarcasspi/PathfindingSearch · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.io.IOException;
import java.util.HashSet;


public class DFID {

    public static final String cutoff = "cutoff";
    public static final String fail = "fail";

    private static long startTime = System.currentTimeMillis();


    public static String findPath(Node start,char goal,boolean clockwise,boolean timer) throws IOException {
//        if(Ex1.board[start.getY()][start.getX()] == goal)
//        {
////            Ex1.output.write(Algorithm.path(start));
////            Ex1.output.write("Num: "+Node.global_index);
////            Ex1.output.write();
//
//
//            return Algorithm.path(start);
//        }
        long startTime = System.currentTimeMillis();

        for (int limit = 1; limit < Ex1.board_size*Ex1.board_size;limit++)
        {
            System.out.println(limit+"<"+Ex1.board_size*Ex1.board_size);
            HashSet<String> H = new HashSet<>();
            String result = Limited_DFS(start,goal,limit,H,clockwise);
            if(result.equals(fail))
            {
                break;
            } else if (!result.equals(cutoff))
            {

                return result;
            }

        }
        Ex1.output.write("no path");
        Ex1.output.write("Num: "+Node.global_index+"\n");
        Ex1.output.write("Cost: inf\n");
        if(Ex1.timer)
        {
            long elapsedTime = System.currentTimeMillis() - startTime;
            double elapsedSeconds = (double)elapsedTime / 1000;
            long miliSecondsDisplay = (elapsedTime) % 60;
            Ex1.output.write(elapsedSeconds+" seconds"+"\n");
        }
        return fail;
    }
    private static String Limited_DFS(Node node, char goal, int limit, HashSet<String> H,boolean clockwise) throws IOException {
        if(goal == node.getTerrain())
        {
            Ex1.output.write(Algorithm.path(node)+"\n");
            Ex1.output.write("Num: "+Node.global_index+"\n");
            Ex1.output.write("Cost: "+node.getCost()+"\n");
            if(Ex1.timer)
            {
                long elapsedTime = System.currentTimeMillis() - startTime;
                double elapsedSeconds = (double)elapsedTime / 1000;
                long miliSecondsDisplay = (elapsedTime) % 60;
                Ex1.output.write(elapsedSeconds+" seconds"+"\n");
            }
            return " ";
        } else if (limit == 0)
        {
            return cutoff;
        }
        else
        {
            H.add(node.getIndex());
            boolean is_cutoff = false;
            Node.Operation[] operations = clockwise ? Node.CLOCKWISE : Node.COUNTER_CLOCKWISE;
            for (int i = 0; i< operations.length; i++)
            {
                Node.Operation op = operations[i];
                int op_cost = node.entry_cost(op);
                if(op_cost>=0)
                {
                    Node child = node.operator(op);
                    if(!H.contains(child.getIndex()))
                    {
                        String result = Limited_DFS(child,goal,limit-1,H,clockwise);
                        if(result.equals(cutoff))
                        {
                            is_cutoff = true;
                        } else if (!result.equals(fail))
                        {
                            return result;
                        }
                    }
                }
            }
            H.remove(node.getIndex());
            if(is_cutoff)
            {
                return cutoff;
            }
            else
            {
                return fail;
            }


        }


    }
}