TLDR
I want to be able to use a rotated area for surface searches.Why?
Currently, we can pass on area, position, radius, and direction. All of these have limitations that either make them unsuitable for my purposes:- "area" will find any entities with any part of their collision_box within the area. However, the area must be a rectangle with a base that's running parallel to the x-axis.
- "position" will find the entity which has that position within its collision_box.
- "position" + "radius" will find any entity within the given radius around the position, iff the entity's center is within the radius.
- "direction" will find any entity in the given direction from a given position, but apparently it's not possible to limit the search distance.
Being able to pass on a position, a bounding box and the orientation of that box would reduce the overhead to calculating bounding box, orientation, and position just once (sometimes they can be directly read from an entity) and just one search. Given that operations handled directly by the game are generally cheaper in terms of computing time than anything that can be done with Lua, this could give a speed boost to mods.
What should this be applied to?
I'm mostly interested in surface.find_entities() and surface.find_entities_filtered(), but there are some other things that are similar enough (basically: any search involving "area") where searching rotated areas would make sense:- find_entities(), find_entities_filtered, count_entities_filtered
- find_tiles_filtered, count_tiles_filtered
- find_units
- find_decoratives_filtered
Use case
Autodrive allows vehicles based on "car" and "spider-vehicle" prototypes to drive autonomously. Sometimes a vehicle will crash into an obstacle that it can't or shouldn't destroy. In this case, it would be stuck because it's still heading into a direction where it can't move. The solution is to let the vehicle bounce off the obstacle until it comes to a stop, and try to repath from that position.The way I currently do the bouncing is rather naive: If a vehicle can't go on, I give it a fixed negative bounce speed, and make this speed positive if the vehicle already was in reverse. However, it could happen that a bouncing vehicle would crash into something else and bounce off that again, with the same fixed speed, eventually being stuck in a state where it continually moves between the same two positions.
Now I want to improve this, especially in regard to crashes of a vehicle with another one. In order to calculate the bounce speeds in a (somewhat) reasonable way, I must know whether they've crashed while driving towards each other (front/front or front/back while reversing) or in the same direction (front/back or front/front while reversing). Therefore, I must check whether the damaged vehicle is in front of or behind the one that caused the crash (and vice versa).
The following screenshots visualize the way searching for entities is done. The thin red lines are the collision boxes (activated via debug settings). The white lines are the x- and y-axes of the vehicles, with the vehicle center as position {0, 0}. Yellow drawings show the search area in front, red drawings (thick lines) the search area at the back of a vehicle. The text at the bottom left indicates where each vehicle found the other one ("front", "back", or "nil").
I started out by looking in a circle (diameter: the smaller side of the vehicle bounding box) just a bit outside of the vehicle's collision_box. This wasn't reliable if the other entity's center wasn't within the circle. Increasing the radius also isn't feasible because then entities might be found while looking ahead although they were actually behind:
- Tank doesn't see car, car doesn't see tank.
- crash_radius.png (1.72 MiB) Viewed 841 times
Then I decided to use area searches if a vehicle was oriented in one of the four cardinal directions (vehicle.orientation: 0, 0.25, 0.5, 0.75). This works, but I can only use this in exceptional cases as the vehicles will be oriented differently most of the time:
- Tank doesn't see car searching within radius when car center is outside the circle. Car searching by area sees tank.
- radius+area.png (1.98 MiB) Viewed 841 times
A further improvement was looking at positions in a straight line from the vehicle center in the direction given by vehicle.orientation. If the first search doesn't find anything it may be because the angle is too awkward and the point isn't within the other vehicle's collision_box yet, so I extend the distance up to 5 times before giving up. This will work most of the time:
- Searching by position, both tank and car can see each other.
- crash_points.png (2.44 MiB) Viewed 841 times
However, there are cases where the two vehicles are at such an angle to each other that searching in one line from the center of a vehicle will never find the other one:
- Tank doesn't see car looking ahead in straight line. Car searching an area sees the tank.
- crash_points_center.png (1.43 MiB) Viewed 841 times
I could work around this by searching a grid: Suppose the collision_box is a rectangle with points A, B, C, D (counting counterclockwise from bottom_left). Go from vehicle center to the center of the line B-C. If nothing turns up there, look at B, if nothing is there look at C. If no entity has been found, extend the search until an area of 3x5 points has been searched. For modded vehicles with a huge collision_box, this search grid may still not be fine-meshed enough, so it may be necessary to add even more search positions in each line.
Basically, having to search in this way is an approximation of searching an arbitrarily rotated box. It could be done, but in a real game (not under lab conditions where the world is empty except for some random entities cheated for testing) this probably would be a UPS-hog. If the game gave us the means to search within rotated areas natively, this would definitely improve performance.
