| | | 1 | | using System.Collections.Generic; |
| | | 2 | | using System.Linq; |
| | | 3 | | using UnityEngine; |
| | | 4 | | |
| | | 5 | | // The cost-based assignment assigns hierarchical objects to each other based on the pairwise costs |
| | | 6 | | // between them. |
| | | 7 | | public class CostBasedAssignment : AssignmentBase { |
| | | 8 | | // Delegate for determining the cost of an assignment between two hierarchical objects. |
| | | 9 | | public delegate float CostDelegate(IHierarchical first, IHierarchical second); |
| | | 10 | | |
| | | 11 | | // Delegate for performing the assignment. |
| | | 12 | | public delegate Plugin.StatusCode AssignDelegate(int numFirst, int numSecond, float[] costs, |
| | | 13 | | int[] assignedFirsts, int[] assignedSeconds, |
| | | 14 | | out int numAssignments); |
| | | 15 | | |
| | | 16 | | // Maximum cost to prevent overflow. |
| | | 17 | | private const float _maxCost = 1e12f; |
| | | 18 | | |
| | | 19 | | private readonly CostDelegate _costFunction; |
| | | 20 | | private readonly AssignDelegate _assignFunction; |
| | | 21 | | |
| | 0 | 22 | | public CostBasedAssignment(CostDelegate costFunction, AssignDelegate assignFunction) { |
| | 0 | 23 | | _costFunction = costFunction; |
| | 0 | 24 | | _assignFunction = assignFunction; |
| | 0 | 25 | | } |
| | | 26 | | |
| | | 27 | | // Run the assignment algorithm and assign the hierarchical objects. |
| | | 28 | | public override List<AssignmentItem> Assign(IReadOnlyList<IHierarchical> first, |
| | 0 | 29 | | IReadOnlyList<IHierarchical> second) { |
| | 0 | 30 | | int numFirst = first.Count; |
| | 0 | 31 | | int numSecond = second.Count; |
| | 0 | 32 | | if (numFirst == 0 || numSecond == 0) { |
| | 0 | 33 | | return new List<AssignmentItem>(); |
| | | 34 | | } |
| | | 35 | | |
| | | 36 | | // Find all pairwise assignment costs. |
| | 0 | 37 | | var assignmentCosts = new float[numFirst * numSecond]; |
| | 0 | 38 | | for (int firstIndex = 0; firstIndex < numFirst; ++firstIndex) { |
| | 0 | 39 | | for (int secondIndex = 0; secondIndex < numSecond; ++secondIndex) { |
| | 0 | 40 | | float cost = _costFunction(first[firstIndex], second[secondIndex]); |
| | 0 | 41 | | float clampedCost = Mathf.Clamp(cost, -_maxCost, _maxCost); |
| | 0 | 42 | | if (cost != clampedCost) { |
| | 0 | 43 | | Debug.LogWarning($"Assignment cost was clamped from {cost} to {clampedCost}."); |
| | 0 | 44 | | } |
| | 0 | 45 | | assignmentCosts[firstIndex * numSecond + secondIndex] = clampedCost; |
| | 0 | 46 | | } |
| | 0 | 47 | | } |
| | | 48 | | |
| | | 49 | | // Solve the assignment problem. |
| | 0 | 50 | | var assignedFirstIndices = new int[numFirst]; |
| | 0 | 51 | | var assignedSecondIndices = new int[numFirst]; |
| | 0 | 52 | | Plugin.StatusCode status = |
| | | 53 | | _assignFunction(numFirst, numSecond, assignmentCosts, assignedFirstIndices, |
| | | 54 | | assignedSecondIndices, out int numAssignments); |
| | 0 | 55 | | if (status != Plugin.StatusCode.StatusOk) { |
| | 0 | 56 | | Debug.LogError( |
| | | 57 | | $"Failed to run the assignment with status code {status}. " + |
| | | 58 | | $"Number of first: {numFirst}, number of second: {numSecond}, " + |
| | | 59 | | $"minimum cost: {assignmentCosts.Min()}, maximum cost: {assignmentCosts.Max()}."); |
| | 0 | 60 | | return new List<AssignmentItem>(); |
| | | 61 | | } |
| | | 62 | | |
| | 0 | 63 | | var assignments = new List<AssignmentItem>(); |
| | 0 | 64 | | for (int i = 0; i < numAssignments; ++i) { |
| | 0 | 65 | | int firstIndex = assignedFirstIndices[i]; |
| | 0 | 66 | | int secondIndex = assignedSecondIndices[i]; |
| | 0 | 67 | | assignments.Add( |
| | | 68 | | new AssignmentItem { First = first[firstIndex], Second = second[secondIndex] }); |
| | 0 | 69 | | } |
| | 0 | 70 | | return assignments; |
| | 0 | 71 | | } |
| | | 72 | | } |