I'm currently trying to program an angle and edge detection circuitry that should be able to detect angles and edges on a graph.
The chart data structure is built from a 2d char array, which may look like this. The size of this example is 10 rows and 9 columns. (White spaces fill the rest of the missing, I couldn't add spaces at the borders ...?)
... ..Y..... ..Y . ZYZ.ZZ .Y .... .M ..
A node is created for each character in the node, and the complete graph is saved as a vector<Node> graph .
Each node is defined as such
struct Node { char character; pair<int,int> position; bool lock; vector<Vertex> adjacent; }; struct Vertex { Node *current; Node *nextTo; };
So, I have many nodes, but some of them are redundant in my use case, for which each node has bool lock =>, telling the systems that these nodes should be ignored.
The nodes that I want to ignore are those that have a symbol . , on the map and placed in an angular position (the node itself has 2 neighboring (neighboring size vector == 2)) or nodes with a symbol . which is between two corners. If another character occurs between two corners, only the corners will be locked. when passing the adjacent corner of the node (search for the second corner), and the node has 4 adjacent nodes, only the first corner will be blocked, which should be locked.
So, I wrote this in some code that turned out to be like that.
for(auto graph_it = begin(graph); graph_it != end(graph); graph_it++) { if(graph_it->adjacent.size() == 2 && graph_it->character == '.') { vector<Node*> trace; cout << "corner found " <<"("<< graph_it->position.first <<","<< graph_it->position.second << ")" << endl; graph_it->lock = true; for (Vertex edge : graph_it->adjacent) { cout << "Check neighbour direction" << endl; int changeX = 0; int changeY = 0; changeX = graph_it->position.first - edge.nextTo->position.first; changeY = graph_it->position.second - edge.nextTo->position.second; cout << "neighbour direction is first: " << changeX << changeY << endl; auto start_position = edge.nextTo; vector<Node*> trace; bool endIsCorner = false; bool conditionMet = false; cout << endl; while((start_position->adjacent.size() != 2|| start_position->adjacent.size() != 4) ) { for(Vertex traversing_edge : start_position->adjacent) { cout <<"position before: " << graph_it->position.first << graph_it->position.second << " now position: "<< start_position->position.first << start_position->position.second << " change is: " << (start_position->position.first - traversing_edge.nextTo->position.first) << " " << start_position->position.second - traversing_edge.nextTo->position.second << " character is: " << traversing_edge.nextTo->character << endl; if (traversing_edge.nextTo->adjacent.size() == 2) { cout << "error found case 1" << endl; cout << "position: " << traversing_edge.nextTo->character << traversing_edge.nextTo->position.first << traversing_edge.nextTo->position.second << endl; start_position = traversing_edge.nextTo; start_position->lock =true; trace.push_back(start_position); endIsCorner = true; conditionMet = true; break; } else if(traversing_edge.nextTo->adjacent.size() == 4) { cout << "error found case 2" << endl; cout << "position: " << traversing_edge.nextTo->character << traversing_edge.nextTo->position.first << traversing_edge.nextTo->position.second << endl; conditionMet = true; break; } if (start_position->position.first - traversing_edge.nextTo->position.first == changeX && start_position->position.second - traversing_edge.nextTo->position.second == changeY) { if (traversing_edge.nextTo->adjacent.size() == 3 ) { start_position = traversing_edge.nextTo; cout << "traversed to position: " << start_position->position.first << start_position->position.second <<" character: "<<start_position->character<< endl; trace.push_back(start_position); } if (traversing_edge.nextTo->adjacent.size() == 2) { edge.nextTo->lock = true; start_position = traversing_edge.nextTo; cout << "traversed to position being corner: " << start_position->position.first << start_position->position.second <<" character: "<<start_position->character<< endl; trace.push_back(start_position); endIsCorner = true; } if (traversing_edge.nextTo->adjacent.size() == 4) { cout << "traversed something else: " << start_position->position.first << start_position->position.second <<" character: "<<start_position->character<< endl; start_position = traversing_edge.nextTo; } } cout << endl; } if (conditionMet) { break; } } if (endIsCorner == true) { for(auto traced: trace) { cout << "Traced for locking position: " <<traced->position.first << traced->position.second << traced->character<< endl; if (traced->character == '.') { cout << "locking position: " <<traced->position.first << traced->position.second << traced->character<< endl; traced->lock = true; } } } else { trace.empty(); endIsCorner = false; } cout<<endl; } } cout << endl; } cout << "Locks detected" << endl;
As I understand it, the code did not do as I want, I started debugging it.
So, the first strange thing I saw is this. The first node that it defines as an angle is the one that is on line 2 and column 1, which is correct.
Then it tries to move in the direction of the first nextTo node of the direction that is below it (line 3, col 2), which is also angular, but somehow it enters the while loop? which I do not understand. Its adjacent vector size is 2, which the debugger also says, but somehow in the while loop it determines the size of 2 and exits the while loop correctly and sets it so that the node is locked .... (Release possible)
Like all this, I check the full schedule to see if things are locked that should be locked ... what is wrong.
for(auto node : graph) { cout << "node position: " <<"(" << node.position.first << "," << node.position.second << ")" << " " << node.character << endl; if (node.locked) { cout << node.position.first << node.position.second << endl; } }
Why do I get this conclusion
node position: (2,1) . 21 node position: (3,1) . 31 node position: (2,2) . node position: (3,2) . node position: (4,2) Z node position: (5,2) . 52 node position: (6,2) . node position: (7,2) . 72 node position: (2,3) Y node position: (3,3) Y node position: (4,3) Y node position: (5,3) Y node position: (6,3) M node position: (7,3) . 73 node position: (2,4) . 24 node position: (4,4) Z node position: (2,5) . 25 node position: (4,5) . node position: (5,5) . 55 node position: (1,6) . 16 node position: (2,6) . node position: (4,6) Z node position: (5,6) . node position: (1,7) . node position: (2,7) . node position: (3,7) . 37 node position: (4,7) . node position: (5,7) . 57 node position: (1,8) . 18 node position: (2,8) . 28 node position: (4,8) Z 48 node position: (5,8) . 58
This means that it blocks not only those that I want to block (being a symbol . That I placed in the specified location), but also those that I do not want to block (symbols other than . ).
(5,2) should not be locked (2,4) should not be locked (2,5) should not be locked (1,7) should be locked (4,7) should be locked
What is wrong here. I am sure that this should be due to a problem that I found in my debugger, but I do not understand why this is happening at all?
--- Update -
I seem to have found another problem as shown here.
corner found (7,2) Check neighbour direction neighbour direction is first: 10 position before: 72 now position: 62 change is: 1 0 Element is: . traversed in right direction . traversed to position: 52 Element: . position before: 72 now position: 52 change is: -2 0 Element is: . error found case 1 position: .72
This is inferred from the while loop.
while((start_position->adjacent.size() != 2|| start_position->adjacent.size() != 4) ) { for(Vertex traversing_edge : start_position->adjacent) { .. }
I change the start_position value in the for loop, how will the loop react to this? .. In my head, it should start all over again and start from the very beginning, and not continue iterating the first vector of the beginning.
Does it have while instead of for ?
start_position starts with a node placed in (7.2), then it goes to node right (6.2) and becomes the new start_position . Then it goes right again (5,2), and start_position becomes the following: node. But the traversing_edge variable becomes a node placed in (7.2) and therefore ends incorrectly. traversing_edge becomes impossible, because the nodes adjacent to the node placed in (5,2) have only neighbors (4,2), (6,2), (5,3) ... So something is definitely wrong here. .
- Update -
DDD DY...D DY . ZYZ.ZZ .Y DDDD .M DD
No nodes have an adjacent vector of size 1, nodes with space characters are also created. D shows which nodes should be locked.
--- Lamda update ---
This card is sokoban, and M is a man, and Y is a diamond, and Z is a target. The idea is that M pushes Y in a certain direction, but in order to prevent the diamond from moving to a position where it cannot be restored again, this circuit will project the graph so that this position is ignored.