Changeset View
Changeset View
Standalone View
Standalone View
ps/trunk/binaries/data/mods/public/maps/random/rmgen/math.js
| Show First 20 Lines • Show All 112 Lines • ▼ Show 20 Lines | function getPointsInBoundingBox(boundingBox) | ||||
| let points = []; | let points = []; | ||||
| for (let x = boundingBox.min.x; x <= boundingBox.max.x; ++x) | for (let x = boundingBox.min.x; x <= boundingBox.max.x; ++x) | ||||
| for (let y = boundingBox.min.y; y <= boundingBox.max.y; ++y) | for (let y = boundingBox.min.y; y <= boundingBox.max.y; ++y) | ||||
| points.push(new Vector2D(x, y)); | points.push(new Vector2D(x, y)); | ||||
| return points; | return points; | ||||
| } | } | ||||
| /** | /** | ||||
| * Sorts the given (x, y) points so that the distance between neighboring points becomes minimal (similar to the traveling salesman problem). | * Get the order of the given points to get the shortest closed path (similar to the traveling salesman problem). | ||||
| * @param {Vectro2D[]} points - Points the path should go through | |||||
| * @returns {number[]} Ordered indices, same length as points | |||||
| */ | */ | ||||
| function sortPointsShortestCycle(points) | function sortPointsShortestCycle(points) | ||||
| { | { | ||||
| let order = []; | let order = []; | ||||
| let distances = []; | let distances = []; | ||||
| if (points.length <= 3) | if (points.length <= 3) | ||||
| { | { | ||||
| for (let i = 0; i < points.length; ++i) | for (let i = 0; i < points.length; ++i) | ||||
| order.push(i); | order.push(i); | ||||
| return order; | return order; | ||||
| } | } | ||||
| // Just add the first 3 points | // Just add the first 3 points | ||||
| let pointsToAdd = points.map(p => p.clone()); | let pointsToAdd = points.map(p => p.clone()); | ||||
| for (let i = 0; i < 3; ++i) | for (let i = 0; i < 3; ++i) | ||||
| { | { | ||||
| order.push(i); | order.push(i); | ||||
| pointsToAdd.shift(i); | pointsToAdd.shift(); | ||||
| if (i) | if (i) | ||||
| distances.push(Math.euclidDistance2D(points[order[i]].x, points[order[i]].y, points[order[i - 1]].x, points[order[i - 1]].y)); | distances.push(points[order[i]].distanceTo(points[order[i - 1]])); | ||||
| } | } | ||||
| distances.push(points[order[0]].distanceTo(points[order[order.length - 1]])); | distances.push(points[order[0]].distanceTo(points[order[order.length - 1]])); | ||||
| // Add remaining points so the path lengthens the least | // Add remaining points so the path lengthens the least | ||||
| let numPointsToAdd = pointsToAdd.length; | let numPointsToAdd = pointsToAdd.length; | ||||
| for (let i = 0; i < numPointsToAdd; ++i) | for (let i = 0; i < numPointsToAdd; ++i) | ||||
| { | { | ||||
| Show All 25 Lines | |||||
Wildfire Games · Phabricator