I have some problems getting an algorithm for my game and hope someone here can help me. Google did not seem to help much, since most solutions just work for a complete tile.
In game units, they can occupy different positions inside the tile, that is, they can be in the upper left corner, in the center, in the lower right corner, ... the position of the tile (2/3), i.e. (2.2 / 3.1), (2.5 / 3.5), (2.8 / 3.9).
If they move from position (2.2 / 3.1) to (5.7 / 4.1), I need a check to see if there is an obstacle in the way.
My current algorithm is:
- Starting from (2.2 / 3.1)
- Calculate the angle of movement (i.e. 70 degrees)
- Move 0.1 steps in this direction.
- Check which plate I find on (floor (pX) / floor (pY))
- Repeat with 2
This algorithm works, but for me it doesn’t look very effective, since an obstacle can only be a complete tile, and not part of the tile (units do not collide). If I increase the step size, I will start skipping tiles that intersect a little (i.e. you only intersect the bottom left corner). Even with a step size of 0.1, you can still skip an obstacle.
I tried to find a solution to take a sub-map (all tiles with corners (floor (start.X) / floor (start.Y)) and (ceil (start.X) / ceil (start.Y)), move around each tile and check mathematically if it intersects. Unfortunately, it seems to me that the required mathematical knowledge is not enough for this check.
My last idea was to take all 4 borders of the tile as a string and make the intersection of the lines, but this seems slower than my original approach.
Any clues?
.