Solved

A relatively simple grid question

Posted on 2000-03-01
11
193 Views
Last Modified: 2010-04-15
Ok, I assume this will be simple to answer, but I forgot most of my algebra equations and don't have a reference. In a game I'm making is a battle-mode which takes place on a grid.

Here's a legend of a sample battlefield layout(in text of course)
A - archer
1 - random enemy #1
2 - random enemy #2
T - target
[  ] - empty space

[  ][  ][  ][  ][  ][  ][  ][  ][  ][  ]              coords:
[  ] A [  ][  ][  ][  ] 2 [  ][  ][  ]        A: 1, 1     2: 6, 1
[  ][  ][  ][  ][  ][  ] 1  T [  ][  ]       1: 6, 2      T: 7, 2    

I want to fire an arrow at the target, but there are two other enemies in the way. Which one is hit? I need some sort of algorythm to figure out which square is in the path's way.

The calculation obviously won't be as precise as deciding if a bullet passed between the enemy's legs as it would in MDK(FPS game), but I need something that can figure trajectory on a simplified scale.

I appologize to the impatient who understood the question within a few sentances, I just didn't want to explain myself a hundred times. Thanks.
 
Also, if someone would like to add an algorythm or bit of code to show the arrow's range radius in grid format, I'd appreciate it.
0
Comment
Question by:lunarred
  • 4
  • 3
  • 3
  • +1
11 Comments
 
LVL 84

Expert Comment

by:ozo
Comment Utility
Are you sure that one of them will be hit?
0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
This looks more like geometry than algebra, but here goes.

I think I would approach it as follows:

The line connecting A to T must cross from row 1 to row 2. Before the crossing it is proceeding through squares in row 1, after the crossing in row 2. It will cross at the midpoint between A and T. So that is halfway across 4,1 it will cross into 4,2. So in total it will proceed through 2,1  3,1  4,1  4,2  5,2  6,2  7,2. So anybody standing in one of those squares could be "hit". You could automatically hit them, or maybe use a random number and a percentage probability of them being hit (maybe the probability decreases with range).

To generalize the process, you should consider the number of rows separating the archer and the target. In the example it is one row, and so the "crossing" happens in the middle. If it were two rows there would be two crossings at a third of the way each, for three rows, three crossing at a quarter of the way, etc. etc.
0
 
LVL 2

Expert Comment

by:_lychee_
Comment Utility
find vector AT (ie. T - A) then swap x and y and negate one of x or y
eg. (3, 4) will become (4, -3) or (-4, 3) -- doesn't matter...
then make this vector 1 and dot it with A1 or A2. this will be the perpendicular distance of 1 from AT or 2 from AT respectively; then to see if there's a 'hit' i guess u can assume 1 and 2 are roundish and see if the distance is less than a certain value?
0
 
LVL 2

Expert Comment

by:_lychee_
Comment Utility
to find out which of the 'hit' ones is closer to A just dot AT with A1 or A2 and see which is smaller....
0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
Oh, and the second question. Might be easiest to approach the other way around, i.e. for any particular target, is it in range? The answer would be given by Pythagoras:

rangesq=rowdistance**2+coldistance**2;

i.e. the rangesquared is equal to the distance along the row squared + the distance along the column squared. Then take the square root of the result to get the actual range.

In the example that would be:

rs=(7-1)**2-(2-1)**2;
rs=36-1;
rs=35;
So the range is 5.916.
You can use sqrt in the standard library.
0
Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 16

Expert Comment

by:imladris
Comment Utility
Note: I am assuming a distance of one for each coordinate.
0
 

Author Comment

by:lunarred
Comment Utility
Ok, these answers are helping alot, but I just wanted to add one thing to make sure I'm clear on this. I mentioned algebra because I remember working with grids in algebra class. I want to make sure I'm working with slopes in the equation(they are 'slopes' right? I'm not sure). If I remember right a slope goes (x, y), so A-T's slope is 6, -1?
Is there a way I could figure that in? I'm used to C's convention at starting with 0 so I'm not even sure if that slope is right. Assuming that is right,  A-Enemy 1's slope is 5, -1 and A-Enemy 2's slope is 5, 0. Could you show me how these would factor in if possible? Thanks.

ps. this is my first question at this site so I'm sorry to reject the answer even though it is very helpful. I'm not sure if accepting it will close the discussion.
0
 
LVL 2

Expert Comment

by:_lychee_
Comment Utility
the slope depends on how u define ur coordinate system... in ur qn u defined it as going right and down from the top-left corner, so the vector AT is (6, 1)

doesn't matter if u stick to 1 convention thruout... it's like flipping ur normal coord sys... the distances are still preserved...
0
 

Author Comment

by:lunarred
Comment Utility
I know, but can I use the slope in an equation to figure if A1 or A2's slope is closest to AT's.
0
 
LVL 16

Accepted Solution

by:
imladris earned 150 total points
Comment Utility
I'm no whiz at this, but it seems to me that if you're going to go the algebraic route (rather than the constructive one which I proposed) you're going to wind up with systems of equations.

E.g. the equation describing the line joining A and T would be:

6y-x=5

(6, -1 describes the slope, for the constant, fill in 1 and 1 for x and y, setting the result as the constant makes it run through 1,1)

The next step is figuring the distance from 1 to the line AT. To do this, you set up the equation for a line running perpendicular to AT and through 1:

y+6x=38

(reverse the slope, and set the constant to the result for 6,2 to make it run through there)

Now you need to calculate where the two lines intersect. This can be done by solving the two equations simultaneously:

6y-x=5
y+6x=38

x=6y-5
y+6(6y-5)=38

y+36y-30=38
37y=68
y=68/37

x=6(68/37)-5
x=408/37-5
x=223/37

So x=6.027 and y=1.838

Now you can calculate the distance between 1 and AT using pythagoras again:

xd**2+yd**2=d**2
0.027**2+0.162**2=0.000729+0.026244=0.026973

So d=sqrt(0.026973)
   d=0.164

And based on that distance you can decide whether 1 was hit or not.

I can do this by hand well enough. However, I can't remember any handy methods for programming algorithms to solve simultaneous equations. (In fact I remember it being related to linear programming, which was some very clever trial and error which normally worked).
0
 

Author Comment

by:lunarred
Comment Utility
Thank you, the question was a bit harder than I thought. You've given me a good point to write some parallel code.
0

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

763 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

7 Experts available now in Live!

Get 1:1 Help Now