# Neghbourhood search algorithm

a guest
Jun 26th, 2016
113
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. //To run, call getNonEmptyCells with desired integer N.
2. //Grab results from foundCells var.
3. //If needed, add new non-empty points to getCell method;
4.
5. var foundCells = {};
6. var processedCells = {};
7.
8. function getNonEmptyCells(N) {
9.     var processingQueue = [];
10.     processingQueue.push(new Point(0, 0));
11.     while(processingQueue.length > 0) {
12.         processNeighbours(processingQueue.pop(), processingQueue, N);
13.     }
14.     //Change to other output if needed
15.     //console.log(foundCells);
16. }
17.
18. function processNeighbours(point, queue, N) {
19.     var searchAreaLeftBound = point.x - N - 1;
20.     var searchAreaRightBound = point.x + N + 1;
21.     var searchAreaUpperBound = point.y - N - 1;
22.     var searchAreaLowerBound = point.y + N + 1;
23.     for (var pX = searchAreaLeftBound; pX <= searchAreaRightBound; pX++) {
24.         for(var pY = searchAreaUpperBound; pY <= searchAreaLowerBound; pY++) {
25.             var potentialPoint = new Point(pX, pY);
26.             if (!processedCells[potentialPoint.toString()]) {
27.                 processedCells[potentialPoint.toString()] = true;
28.                 if(getCellByPoint(potentialPoint)) {
29.                     foundCells[potentialPoint.toString()] = true;
30.                     queue.push(potentialPoint);
31.                 }
32.             }
33.         }
34.     }
35. }
36.
37. ///// HELPER STRUCTURES /////
38.
39. function Point(x, y) {
40.     this.x = x;
41.     this.y = y;
42. }
43.
44. Point.prototype.toString = function() {
45.     return this.x + ";" + this.y;
46. }
47.
48. function getCellByPoint(point) { return getCell(point.x, point.y); }
49.
50. function getCell(x, y) {
51.     //Black box, returns true for predifined pairs of x and y
52.     switch (x + ";" + y) {
53.         case "-2;2": return true;
54.         case "1;6": return true;
55.         case "8;9": return true;
56.         case "-8;0": return true;
57.         case "-7;0": return true;
58.         case "-6;0": return true;
59.         case "-5;0": return true;
60.         case "-4;0": return true;
61.         case "-3;0": return true;
62.         case "-2;0": return true;
63.         case "-1;0": return true;
64.         case "0;0": return true;
65.         case "1;0": return true;
66.         case "2;0": return true;
67.         case "3;0": return true;
68.         case "4;0": return true;
69.         case "5;0": return true;
70.         case "6;0": return true;
71.         case "7;0": return true;
72.         case "8;0": return true;
73.         case "0;8": return true;
74.         case "0;7": return true;
75.         case "0;6": return true;
76.         case "0;5": return true;
77.         case "0;4": return true;
78.         case "0;3": return true;
79.         case "0;2": return true;
80.         case "0;1": return true;
81.         case "0;-1": return true;
82.         case "0;-2": return true;
83.         case "0;-2": return true;
84.         case "0;-3": return true;
85.         case "0;-4": return true;
86.         case "0;-5": return true;
87.         case "0;-6": return true;
88.         case "0;-7": return true;
89.         case "0;-8": return true;
90.         default: return false;
91.     }
92. }