Changeset View
Changeset View
Standalone View
Standalone View
source/simulation2/helpers/PathGoal.cpp
| /* Copyright (C) 2018 Wildfire Games. | /* Copyright (C) 2019 Wildfire Games. | ||||
| * This file is part of 0 A.D. | * This file is part of 0 A.D. | ||||
| * | * | ||||
| * 0 A.D. is free software: you can redistribute it and/or modify | * 0 A.D. is free software: you can redistribute it and/or modify | ||||
| * it under the terms of the GNU General Public License as published by | * it under the terms of the GNU General Public License as published by | ||||
| * the Free Software Foundation, either version 2 of the License, or | * the Free Software Foundation, either version 2 of the License, or | ||||
| * (at your option) any later version. | * (at your option) any later version. | ||||
| * | * | ||||
| * 0 A.D. is distributed in the hope that it will be useful, | * 0 A.D. is distributed in the hope that it will be useful, | ||||
| Show All 11 Lines | |||||
| #include "graphics/Terrain.h" | #include "graphics/Terrain.h" | ||||
| #include "Pathfinding.h" | #include "Pathfinding.h" | ||||
| #include "Geometry.h" | #include "Geometry.h" | ||||
| static bool NavcellContainsCircle(int i, int j, fixed x, fixed z, fixed r, bool inside) | static bool NavcellContainsCircle(int i, int j, fixed x, fixed z, fixed r, bool inside) | ||||
| { | { | ||||
| // Accept any navcell (i,j) that contains a point which is inside[/outside] | // Accept any circle (x, z, r) that contains a point which is: | ||||
Stan: Maybe this could be doxygen on the top of the function :) | |||||
| // (or on the edge of) the circle | // - strictly inside the navcell | ||||
Not Done Inline ActionsSeeing this I assume the second possibility? bb: Seeing this I assume the second possibility? | |||||
| // - exactly on the left/top edge of the navcell | |||||
| // (and vice-versa if inside is false). | |||||
| // We pick the left/top edges as this avoids ambiguity: a point can only belong to one navcell. | |||||
Not Done Inline Actionsleft/upper edge of a circle, sounds like a joke we tell about Belgians here. Do you mean something like upper circle half, or the left/upper side of the navcell? bb: `left/upper edge of a circle`, sounds like a joke we tell about Belgians here. Do you mean… | |||||
Done Inline ActionsI mean the latter indeed. Comment sorta makes sense for squares. wraitii: I mean the latter indeed. Comment sorta makes sense for squares. | |||||
Not Done Inline ActionsNow the written condition is true for about every navcell: a navcell is not supposed to be empty, so it will always contain "a" point... When you change navcell (i,j) to circle (x,z,r) the comment looks more correct side => edge similar for the square below bb: Now the written condition is true for about every navcell: a navcell is not supposed to be… | |||||
| // Get world-space bounds of navcell | |||||
| entity_pos_t x0 = entity_pos_t::FromInt(i).Multiply(Pathfinding::NAVCELL_SIZE); | entity_pos_t x0 = entity_pos_t::FromInt(i).Multiply(Pathfinding::NAVCELL_SIZE); | ||||
| entity_pos_t z0 = entity_pos_t::FromInt(j).Multiply(Pathfinding::NAVCELL_SIZE); | entity_pos_t z0 = entity_pos_t::FromInt(j).Multiply(Pathfinding::NAVCELL_SIZE); | ||||
| entity_pos_t x1 = x0 + Pathfinding::NAVCELL_SIZE; | entity_pos_t x1 = x0 + Pathfinding::NAVCELL_SIZE - fixed::Epsilon(); | ||||
| entity_pos_t z1 = z0 + Pathfinding::NAVCELL_SIZE; | entity_pos_t z1 = z0 + Pathfinding::NAVCELL_SIZE - fixed::Epsilon(); | ||||
| if (inside) | if (inside) | ||||
| { | { | ||||
| // Get the point inside the navcell closest to (x,z) | // Get the point inside the navcell closest to (x, z) | ||||
| entity_pos_t nx = Clamp(x, x0, x1); | entity_pos_t nx = Clamp(x, x0, x1); | ||||
| entity_pos_t nz = Clamp(z, z0, z1); | entity_pos_t nz = Clamp(z, z0, z1); | ||||
| // Check if that point is inside the circle | // Check if that point is inside the circle | ||||
| return (CFixedVector2D(nx, nz) - CFixedVector2D(x, z)).CompareLength(r) <= 0; | return (CFixedVector2D(nx, nz) - CFixedVector2D(x, z)).CompareLength(r) <= 0; | ||||
| } | } | ||||
| else | else | ||||
| { | { | ||||
| // If any corner of the navcell is outside the circle, return true. | // If any corner of the navcell is outside the circle, return true. | ||||
| // Otherwise, since the circle is convex, there cannot be any other point | // Otherwise, since the circle is convex, there cannot be any other point | ||||
| // in the navcell that is outside the circle. | // in the navcell that is outside the circle. | ||||
| return ( | return ( | ||||
| (CFixedVector2D(x0, z0) - CFixedVector2D(x, z)).CompareLength(r) >= 0 | (CFixedVector2D(x0, z0) - CFixedVector2D(x, z)).CompareLength(r) >= 0 | ||||
| || (CFixedVector2D(x1, z0) - CFixedVector2D(x, z)).CompareLength(r) >= 0 | || (CFixedVector2D(x1, z0) - CFixedVector2D(x, z)).CompareLength(r) >= 0 | ||||
| || (CFixedVector2D(x0, z1) - CFixedVector2D(x, z)).CompareLength(r) >= 0 | || (CFixedVector2D(x0, z1) - CFixedVector2D(x, z)).CompareLength(r) >= 0 | ||||
| || (CFixedVector2D(x1, z1) - CFixedVector2D(x, z)).CompareLength(r) >= 0 | || (CFixedVector2D(x1, z1) - CFixedVector2D(x, z)).CompareLength(r) >= 0 | ||||
| ); | ); | ||||
| } | } | ||||
| } | } | ||||
| static bool NavcellContainsSquare(int i, int j, | static bool NavcellContainsSquare(int i, int j, | ||||
| fixed x, fixed z, CFixedVector2D u, CFixedVector2D v, fixed hw, fixed hh, | fixed x, fixed z, CFixedVector2D u, CFixedVector2D v, fixed hw, fixed hh, | ||||
| bool inside) | bool inside) | ||||
| { | { | ||||
| // Accept any navcell (i,j) that contains a point which is inside[/outside] | // Accept any square (x, z, u, v, hw, hh) that contains a point which is: | ||||
StanUnsubmitted Not Done Inline ActionsSame here. Stan: Same here. | |||||
| // (or on the edge of) the square | // - strictly inside the navcell | ||||
| // - exactly on the left/top edge of the navcell | |||||
| // (and vice-versa if inside is false). | |||||
| // We pick the left/top edges as this avoids ambiguity: a point can only belong to one navcell. | |||||
| // Get world-space bounds of navcell | |||||
| entity_pos_t x0 = entity_pos_t::FromInt(i).Multiply(Pathfinding::NAVCELL_SIZE); | entity_pos_t x0 = entity_pos_t::FromInt(i).Multiply(Pathfinding::NAVCELL_SIZE); | ||||
Not Done Inline Actionsif so then the same comment here bb: if so then the same comment here | |||||
| entity_pos_t z0 = entity_pos_t::FromInt(j).Multiply(Pathfinding::NAVCELL_SIZE); | entity_pos_t z0 = entity_pos_t::FromInt(j).Multiply(Pathfinding::NAVCELL_SIZE); | ||||
| entity_pos_t x1 = x0 + Pathfinding::NAVCELL_SIZE; | entity_pos_t x1 = x0 + Pathfinding::NAVCELL_SIZE - fixed::Epsilon(); | ||||
| entity_pos_t z1 = z0 + Pathfinding::NAVCELL_SIZE; | entity_pos_t z1 = z0 + Pathfinding::NAVCELL_SIZE - fixed::Epsilon(); | ||||
| if (inside) | if (inside) | ||||
| { | { | ||||
| // Get the point inside the navcell closest to (x,z) | // Get the point inside the navcell closest to (x, z) | ||||
| entity_pos_t nx = Clamp(x, x0, x1); | entity_pos_t nx = Clamp(x, x0, x1); | ||||
| entity_pos_t nz = Clamp(z, z0, z1); | entity_pos_t nz = Clamp(z, z0, z1); | ||||
| // Check if that point is inside the circle | // Check if that point is inside the circle | ||||
| return Geometry::PointIsInSquare(CFixedVector2D(nx - x, nz - z), u, v, CFixedVector2D(hw, hh)); | return Geometry::PointIsInSquare(CFixedVector2D(nx - x, nz - z), u, v, CFixedVector2D(hw, hh)); | ||||
| } | } | ||||
| else | else | ||||
| { | { | ||||
| // If any corner of the navcell is outside the square, return true. | // If any corner of the navcell is outside the square, return true. | ||||
| Show All 34 Lines | |||||
| bool PathGoal::NavcellRectContainsGoal(int i0, int j0, int i1, int j1, int* gi, int* gj) const | bool PathGoal::NavcellRectContainsGoal(int i0, int j0, int i1, int j1, int* gi, int* gj) const | ||||
| { | { | ||||
| // Get min/max to simplify range checks | // Get min/max to simplify range checks | ||||
| int imin = std::min(i0, i1); | int imin = std::min(i0, i1); | ||||
| int imax = std::max(i0, i1); | int imax = std::max(i0, i1); | ||||
| int jmin = std::min(j0, j1); | int jmin = std::min(j0, j1); | ||||
| int jmax = std::max(j0, j1); | int jmax = std::max(j0, j1); | ||||
| // Direction to iterate from (i0,j0) towards (i1,j1) | // Direction to iterate from (i0, j0) towards (i1, j1) | ||||
| int di = i1 < i0 ? -1 : +1; | int di = i1 < i0 ? -1 : +1; | ||||
| int dj = j1 < j0 ? -1 : +1; | int dj = j1 < j0 ? -1 : +1; | ||||
| switch (type) | switch (type) | ||||
| { | { | ||||
| case POINT: | case POINT: | ||||
| { | { | ||||
| // Calculate the navcell that contains the point goal | // Calculate the navcell that contains the point goal | ||||
| int i = (x >> Pathfinding::NAVCELL_SIZE_LOG2).ToInt_RoundToNegInfinity(); | int i = (x >> Pathfinding::NAVCELL_SIZE_LOG2).ToInt_RoundToNegInfinity(); | ||||
| int j = (z >> Pathfinding::NAVCELL_SIZE_LOG2).ToInt_RoundToNegInfinity(); | int j = (z >> Pathfinding::NAVCELL_SIZE_LOG2).ToInt_RoundToNegInfinity(); | ||||
| // If that goal navcell is in the given range, return it | // If that goal navcell is in the given range, return it | ||||
| if (imin <= i && i <= imax && jmin <= j && j <= jmax) | if (imin <= i && i <= imax && jmin <= j && j <= jmax) | ||||
| { | { | ||||
| if (gi) | if (gi) | ||||
| *gi = i; | *gi = i; | ||||
| if (gj) | if (gj) | ||||
| *gj = j; | *gj = j; | ||||
| return true; | return true; | ||||
| } | } | ||||
| return false; | return false; | ||||
| } | } | ||||
| case CIRCLE: | case CIRCLE: | ||||
| { | { | ||||
| // Loop over all navcells in the given range (starting at (i0,j0) since | // Loop over all navcells in the given range (starting at (i0, j0) since | ||||
| // this function is meant to find the goal navcell nearest to there | // this function is meant to find the goal navcell nearest to there | ||||
| // assuming jmin==jmax || imin==imax), | // assuming jmin == jmax || imin == imax), | ||||
| // and check whether any point in each navcell is within the goal circle. | // and check whether any point in each navcell is within the goal circle. | ||||
| // (TODO: this is pretty inefficient.) | // (TODO: this is pretty inefficient.) | ||||
| for (int j = j0; jmin <= j && j <= jmax; j += dj) | for (int j = j0; jmin <= j && j <= jmax; j += dj) | ||||
| { | { | ||||
| for (int i = i0; imin <= i && i <= imax; i += di) | for (int i = i0; imin <= i && i <= imax; i += di) | ||||
| { | { | ||||
| if (NavcellContainsCircle(i, j, x, z, hw, true)) | if (NavcellContainsCircle(i, j, x, z, hw, true)) | ||||
| { | { | ||||
| if (gi) | if (gi) | ||||
| *gi = i; | *gi = i; | ||||
| if (gj) | if (gj) | ||||
| *gj = j; | *gj = j; | ||||
| return true; | return true; | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| return false; | return false; | ||||
| } | } | ||||
| case INVERTED_CIRCLE: | case INVERTED_CIRCLE: | ||||
| { | { | ||||
| // Loop over all navcells in the given range (starting at (i0,j0) since | // Loop over all navcells in the given range (starting at (i0, j0) since | ||||
| // this function is meant to find the goal navcell nearest to there | // this function is meant to find the goal navcell nearest to there | ||||
| // assuming jmin==jmax || imin==imax), | // assuming jmin == jmax || imin == imax), | ||||
| // and check whether any point in each navcell is outside the goal circle. | // and check whether any point in each navcell is outside the goal circle. | ||||
| // (TODO: this is pretty inefficient.) | // (TODO: this is pretty inefficient.) | ||||
| for (int j = j0; jmin <= j && j <= jmax; j += dj) | for (int j = j0; jmin <= j && j <= jmax; j += dj) | ||||
| { | { | ||||
| for (int i = i0; imin <= i && i <= imax; i += di) | for (int i = i0; imin <= i && i <= imax; i += di) | ||||
| { | { | ||||
| if (NavcellContainsCircle(i, j, x, z, hw, false)) | if (NavcellContainsCircle(i, j, x, z, hw, false)) | ||||
| { | { | ||||
| if (gi) | if (gi) | ||||
| *gi = i; | *gi = i; | ||||
| if (gj) | if (gj) | ||||
| *gj = j; | *gj = j; | ||||
| return true; | return true; | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| return false; | return false; | ||||
| } | } | ||||
| case SQUARE: | case SQUARE: | ||||
| { | { | ||||
| // Loop over all navcells in the given range (starting at (i0,j0) since | // Loop over all navcells in the given range (starting at (i0, j0) since | ||||
| // this function is meant to find the goal navcell nearest to there | // this function is meant to find the goal navcell nearest to there | ||||
| // assuming jmin==jmax || imin==imax), | // assuming jmin == jmax || imin == imax), | ||||
| // and check whether any point in each navcell is within the goal square. | // and check whether any point in each navcell is within the goal square. | ||||
| // (TODO: this is pretty inefficient.) | // (TODO: this is pretty inefficient.) | ||||
| for (int j = j0; jmin <= j && j <= jmax; j += dj) | for (int j = j0; jmin <= j && j <= jmax; j += dj) | ||||
| { | { | ||||
| for (int i = i0; imin <= i && i <= imax; i += di) | for (int i = i0; imin <= i && i <= imax; i += di) | ||||
| { | { | ||||
| if (NavcellContainsSquare(i, j, x, z, u, v, hw, hh, true)) | if (NavcellContainsSquare(i, j, x, z, u, v, hw, hh, true)) | ||||
| { | { | ||||
| if (gi) | if (gi) | ||||
| *gi = i; | *gi = i; | ||||
| if (gj) | if (gj) | ||||
| *gj = j; | *gj = j; | ||||
| return true; | return true; | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| return false; | return false; | ||||
| } | } | ||||
| case INVERTED_SQUARE: | case INVERTED_SQUARE: | ||||
| { | { | ||||
| // Loop over all navcells in the given range (starting at (i0,j0) since | // Loop over all navcells in the given range (starting at (i0, j0) since | ||||
| // this function is meant to find the goal navcell nearest to there | // this function is meant to find the goal navcell nearest to there | ||||
| // assuming jmin==jmax || imin==imax), | // assuming jmin == jmax || imin == imax), | ||||
| // and check whether any point in each navcell is outside the goal square. | // and check whether any point in each navcell is outside the goal square. | ||||
| // (TODO: this is pretty inefficient.) | // (TODO: this is pretty inefficient.) | ||||
| for (int j = j0; jmin <= j && j <= jmax; j += dj) | for (int j = j0; jmin <= j && j <= jmax; j += dj) | ||||
| { | { | ||||
| for (int i = i0; imin <= i && i <= imax; i += di) | for (int i = i0; imin <= i && i <= imax; i += di) | ||||
| { | { | ||||
| if (NavcellContainsSquare(i, j, x, z, u, v, hw, hh, false)) | if (NavcellContainsSquare(i, j, x, z, u, v, hw, hh, false)) | ||||
| { | { | ||||
| ▲ Show 20 Lines • Show All 143 Lines • Show Last 20 Lines | |||||
Wildfire Games · Phabricator
Maybe this could be doxygen on the top of the function :)