-
-
Save AloiSama/e5b36fa4a25c6506dba0d37896cbeb75 to your computer and use it in GitHub Desktop.
Traveling Salesman Problem - Processing 3.2.4
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Node { | |
| private int x, y; | |
| public Node(int x, int y) { | |
| this.x = x; | |
| this.y = y; | |
| } | |
| public int getX() { | |
| return this.x; | |
| } | |
| public int getY() { | |
| return this.y; | |
| } | |
| public void setX(int x) { | |
| this.x = x; | |
| } | |
| public void setY(int y) { | |
| this.y = y; | |
| } | |
| public void show() { | |
| fill(12, 165, 53); | |
| stroke(165, 237, 185); | |
| strokeWeight(2); | |
| ellipse(x - 5, y - 5, 10, 10); | |
| fill(255); | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //USER INPUT: | |
| private int NODE_COUNT = 10; | |
| //PROGRAM: | |
| private final int WIDTH = 512, HEIGHT = 512; | |
| private ArrayList<Node> nodeList; | |
| private int[] currentOrder, bestOrder; | |
| private float currentDistance = -1, bestDistance = -1; | |
| float curDist; | |
| private ArrayList<String> textToPaint = new ArrayList<String>(); | |
| void setup() { | |
| size(512, 512); | |
| init(); | |
| } | |
| void draw() { | |
| background(0); | |
| drawText(textToPaint); | |
| drawConnections(nodeList, bestOrder, true); | |
| drawConnections(nodeList, currentOrder, false); | |
| drawNodes(nodeList); | |
| swap(floor(random(NODE_COUNT)), floor(random(NODE_COUNT))); | |
| curDist = getNetworkDistance(nodeList, currentOrder); | |
| if (curDist < bestDistance) { | |
| bestOrder = currentOrder.clone(); | |
| bestDistance = curDist; | |
| } | |
| updateTextInfo(); | |
| } | |
| boolean listContainsOrder(ArrayList<int[]> list, int[] order) { | |
| int[] temp; | |
| for (int i = 0; i < list.size(); i++) { | |
| temp = list.get(i); | |
| if (temp == order) { | |
| return true; | |
| } else { | |
| continue; | |
| } | |
| } | |
| return false; | |
| } | |
| void mouseClicked() { | |
| init(); | |
| } | |
| void mouseWheel(MouseEvent event) { | |
| float e = event.getCount(); | |
| if (NODE_COUNT == 1 && e < 0) { | |
| } else { | |
| NODE_COUNT += e; | |
| } | |
| init(); | |
| println(e); | |
| } | |
| void init() { | |
| //CLEAR | |
| textToPaint.clear(); | |
| //INITIALIZE | |
| nodeList = new ArrayList<Node>(NODE_COUNT); | |
| currentOrder = new int[NODE_COUNT]; | |
| bestOrder = new int[NODE_COUNT]; | |
| //RANDOMLY ADD NODE_COUNT NODES TO CANVAS. | |
| int randX; | |
| int randY; | |
| for (int i = 0; i < NODE_COUNT; i++) { | |
| randX = floor(random(WIDTH)); | |
| randY = floor(random(HEIGHT)); | |
| this.nodeList.add(new Node(randX, randY)); | |
| currentOrder[i] = i; | |
| } | |
| bestOrder = currentOrder.clone(); | |
| currentDistance = getNetworkDistance(nodeList, currentOrder); | |
| bestDistance = currentDistance; | |
| textToPaint.add("Current Distance: " + currentDistance); | |
| textToPaint.add("Best Distance: " + bestDistance); | |
| textToPaint.add("Nodes: " + NODE_COUNT); | |
| } | |
| void updateTextInfo() { | |
| textToPaint.set(0, "Current Distance: " + curDist); | |
| textToPaint.set(1, "Best Distance: " + bestDistance); | |
| textToPaint.set(2, "Nodes: " + NODE_COUNT); | |
| } | |
| void swap(int from, int to) { | |
| int temp = currentOrder[from]; | |
| currentOrder[from] = currentOrder[to]; | |
| currentOrder[to] = temp; | |
| } | |
| void drawNodes(ArrayList<Node> toDraw) { | |
| for (int i = 0; i < toDraw.size(); i++) { | |
| toDraw.get(i).show(); | |
| } | |
| } | |
| void drawConnections(ArrayList<Node> toConnect, int[] order, boolean bold) { | |
| noFill(); | |
| if (!bold) { | |
| stroke(255, 0, 0); | |
| } else { | |
| stroke(73, 227, 97); | |
| strokeWeight(5); | |
| } | |
| beginShape(); | |
| for (int i = 0; i < toConnect.size(); i++) { | |
| vertex(toConnect.get(order[i]).getX() - 5, toConnect.get(order[i]).getY() - 5); | |
| } | |
| endShape(); | |
| strokeWeight(2); | |
| noStroke(); | |
| fill(255); | |
| } | |
| void drawText(ArrayList<String> toDraw) { | |
| textSize(20); | |
| fill(255); | |
| for (int i = 0; i < toDraw.size(); i++) { | |
| text(toDraw.get(i), 10, 25 + (25 * i)); | |
| } | |
| } | |
| float getNetworkDistance(ArrayList<Node> nList, int[] order) { | |
| ArrayList<Node> reorderedList = getReordedList(nList, order); | |
| float sum = 0; | |
| for (int i = 0; i < reorderedList.size() - 1; i++) { | |
| sum += dist(reorderedList.get(i).getX(), reorderedList.get(i).getY(), | |
| reorderedList.get(i+1).getX(), reorderedList.get(i+1).getY()); | |
| } | |
| return sum; | |
| } | |
| ArrayList<Node> getReordedList(ArrayList<Node> nList, int[] order) { | |
| ArrayList<Node> reorderedList = new ArrayList<Node>(NODE_COUNT); | |
| for (int i = 0; i < nList.size(); i++) { | |
| reorderedList.add(nList.get(order[i])); | |
| } | |
| return reorderedList; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment