Envision, Create, Share

Welcome to HBGames, a leading amateur game development forum and Discord server. All are welcome, and amongst our ranks you will find experts in their field from all aspects of video game design and development.

Pathfinding Design Question: For Math Whizzes

I've altered the battle system to be A) sideview and to B) move battlers permanently after an attack. So now, instead of Alex rushing to attack a ghost and then returning to his starting position, he stays next to the ghost. Because of this, battlers will scatter across the map, which allows for tactical potential. One such tactical feature is the ability for battlers to 'intercept' enemies en route to a vulnerable ally. The problem I'm having is: where do the two battler's meet?

To give you a better picture of how this works, the battle field is divided into a 10x6 grid. Only one battler can occupy any given space on this grid. Battlers always move in a straight line, even through other battlers. They also move at varying speeds, depending on their agility and the weight of their armor.

Scenario 1: Deadeye is an archer who's vulnerable to melee attack, but can stand at the edge of the battlemap (10, 5) and fire at enemies without having to move. His enemy, Oglaf the viking warrior, decides to rush him from coordinates (3, 5). Deadeye's good buddy Yoyoma (9, 5) decides to intercept. Where do Oglaf and Yoyoma meet? How is this calculated? (Sounds a lot like an SAT question, doesn't it?)

Scenario 2: Things get trickier when the action isn't happening in a straight line. Once again, vulnerable Deadeye is in the back row (10, 5). This time, however, Oglaf is at an angle to him (3, 7), as is Yoyoma (8, 4). Where do they meet? How is this calculated?

Scenario 3: Now let's include speed. Everyone's in the same position, Deadeye (10, 5), Oglaf (3, 7), and Yoyoma (8,4). However, before charging Oglaf puts on his Super Heavy Platemail of Death, while Yoyoma strips off everything, applies some warpaint, and rushes at Oglaf in a beserker's rage. Given that Yoyoma is two times faster than his opponent, where do they meet? How is this calculated?

I figure that trig plays a role in here somewhere, but I foolishly skipped that class to go to calculus, instead. Anyone have an elegant solution to this problem? I know one has to exist, but I'm at an utter loss as to what it could be.

Thanks,
tuatha
 
Interesting problem. The solution isn't easy, and I can only partially help you.

First, take a look at this:
Untitled-1.jpg


The general idea behind this is that the meeting point will be the intersection point between the locus of the points that A and C can reach in the same amount of time, and the straight line from A to B. That locus is a straight line itself if A and C move at the same speed, but it's a complex curve when their speeds are different.

Note that scenario 1 is only a particular case of scenario 2, which can represent any set of initial positions.

The only way I know to solve this needs you to find the equations describing the lines m and n, and solving systems of equations to find intersection points.
The general equation of a straight line is simple:
ax+by+c=0
In scenario 1, assuming A = (3,5) and B = (10,5), the equation of AB is:
y - 5 = 0
In general, when you have two points, (x1,y1) and (x2,y2), in order to determine a, b and c, you need to solve the system
a*x1 + b*y1 + c = 0
a*x2 + b*y2 + c = 0
where you can assign one among a, b, c (if not zero).

Taking the numbers from Scenario 2, for the straight line between Oglaf (3,7) and Deadeye (10,5), you have:

a*3 + b*7* + c = 0 (x5)
a*10 + b*5 + c = 0 (x7)
 
15a + 35b + 5c = 0
70a + 35b + 7c = 0
 
55a + 2c = 0

Now you can fix a=2, and you have c=-55. Go back to one of the two initial equations and you have:
2*3+b*7+(-55)=0 => b = (55-6)/7 = 7
so the equation is:

2x + 7y - 55 = 0  (m)

If you are not sure about the result, you can always verify that the two points belong to this line:
Oglaf: 2*3+7*7-55=0 true
Deadeye: 2*10+7*5-55=0 true

The locus has an equation as well. If s1 and s2 are the two speeds, it is:

s1^2*[(x-x1)^2+(y-y1)^2]=s2^2*[(x-x2)^2+(y-y2)^2]

Again, taking the numbers from Scenario 2, we have the two points Oglaf (3,7) and Yoyoma (8,4), so the equation is:

(x-3)^2+(y-7)^2=(x-8)^2+(y-4)^2
=> x^2 - 6x + 9 + y^2 - 14y + 49 = x^2 -16x + 64 + y^2 -8y + 16
=> 10x-6y-22=0

which is a straight line (n).
The intersection point between (m) and (n) is the meeting point we are looking for. In order to find that, you have to solve the system:

2x + 7y - 55 = 0 (m)
10x - 6y - 22 = 0 (n)

which has a solution (5.9..., 6.17...)

At this point, you have to decide what to do with these non-integer numbers, and select two tiles close to this point. How to do that is up to you.

Finally, in Scenario 3, the equation of the locus is

(x-3)^2+(y-7)^2=2^2*[(x-8)^2+(y-4)^2] (n)

which is not a straight line anymore, and you have to solve the system

2x + 7y - 55 = 0 (m)
(x-3)^2+(y-7)^2=2^2*[(x-8)^2+(y-4)^2] (n)

in order to find the intersection point(s).

In all these cases, you could find one, two, or zero interesection points, and you have to verify if they actually are between "Oglaf" and "Yoyoma".

EDIT: how to do all that with a programming language? i haven't done anything like that before, so i'll pass on this one.
 
Charlie, Excellent!

A couple of thoughts... (I'm messed up! I thought about this lying in bed)

1) solve for the distance along AB as if AB is the X axis, (or AC as the axis) then just calculate that distance along AB in real space.
2) I gets a bit easier once you realize that your complex curve is just a circle.
3) It also gets a little bit interesting since you really don't want both characters to end up on the same tile, but 2 adjacent tiles facing each other... ??
(however, that has more to do with what you do with the characters after you solve the equation.)

Another thought...

Why not just move A 1 unit (tile) along AB, calculate the distance AC, and once they reach the speed ratio you have your point.
The area you're working in is small enough that at most it would be 5 iterations (Assuming A & B are in opposite corners of the grid)
And, the answer is always rounded off to the nearest whole number.

That must be the point where I fell asleep... :scruff:
 

Thank you for viewing

HBGames is a leading amateur video game development forum and Discord server open to all ability levels. Feel free to have a nosey around!

Discord

Join our growing and active Discord server to discuss all aspects of game making in a relaxed environment. Join Us

Content

  • Our Games
  • Games in Development
  • Emoji by Twemoji.
    Top