|
After some more thought about the problem, I realized that while we can't elimenate unnecessary tests altogether, we can cut out a good portion of the tests in some circumstances. This might involve maintaining certain properties before the actual hit testing occurs (like how order is maintained for a balanced search tree before a search is performed).
I will outline my approach below (and you can judge my methods):
- A rectangular plane (named: MAP) is created which everything else will be relative to.
- MAP is subdivided into regions. These regions are squares. They contain references to circles. The length and width of the region are set such that it is not smaller than the largest diameter of a circle. These regions are addressed by indices. The indices are directly related to the region's offset from the origin on MAP.
- A circle (named: CHAR1) is created on MAP with a radius no greater than half a region's length. (This is important later on when we try to determine what regions get tested.)
- CHAR1 is added to the region that it is in. (The circle's boundaries may cross into one or more other regions.) Its region will now have a reference to it.
- CHAR1 moves and it crosses its region's boundaries. It has crossed into another region, so the region's references to CHAR1 are deleted, and the current region CHAR1 resides in creates a reference to CHAR1. (Regions are synchronized with the circle's location.)
- Another circle (named: CHAR2) is created on MAP. It fires a projectile that follows a line (named: PATH).
- Now here is the tricky part (I don't even know if it works.):
- With PATH defined by y = mx + b, create 2 more lines that are parrallel to PATH and are separated by an a perpendicular distance that is equal to the greatest possible radius of a circle (a limit which is artificially imposed). The lines are created on with sides of PATH. The three lines intersect all the regions that should be tested. (Hit-testing with squares should be much more efficient than hit testing with circles.)
- So now that we have 3 lines, we just plugin values for X in increments of the width of the region starting from the position of CHAR2. We get coordinates that hit every region that needs to be tested. Suppose the indices of the regions use the format [x, y] in increments of 1, and region's corner defined by it's coordinates multiplied by the region length/width, then we could do an integer division on the coordinates given by plugging in X values into the line equations and get the regions that should be tested.
ROFLOLMFAO
|
|
|
|
|
Hi,
this sounds reasonable, provided:
1) there are many CHAR1 (otherwise it all does not matter)
2) the greatest possible radius of a circle is small with respect to MAP size
I am not sure about your integer division stuff; the line y = mx + b seems to
imply floating-point: m and b wont be integers.
BTW: the general equation for a line is a*x + b*y + c = 0 which is symmetric in
x and y, resulting in no trouble when the line is vertical (if you dont like having
3 coefficients, you can divide them all by c provided c is non-zero).
Further thought: there is a useful method Region.IsVisible()
you might apply it to a region that is a (non-orthogonal) rectangle starting at
the shooter, pointing in the direction he is shooting, and having a width of
twice "the greatest possible radius of a circle" and a length sufficient to
cross the border of MAP.
Using it you would mean you do not need your squares after all, simply test each
circle's center against it (very simple, probably fast too).
As a side effect you could shoot circles that are off-screen too (by making the
rectangle length quite large) !
|
|
|
|
|
Thanks for your responses. I'll try to work with different approaches to fidn the best one. (It's a Windows Presentation Foundation application by the way. It's also network-oriented. The game engine runs on the server.)
As for the integer division stuff, I'll probably cast the Double to an Int64, strip the fractional part, or round down after division — whichever is more efficient.
ROFLOLMFAO
|
|
|
|
|
Just to ensure that you know that testing for intersection with circles is reasonably inexpensive:
if floating point, normalise equation of line
ax + by + c = 0
so that a^2+b^2=1
then the test for intersection with circle centre (x0,y0) radius r0 is
abs(a*x0 + b*y0 + c) <= r0
If integers, then there are several ways, but
(a*x0 + b*y0 +c)^2 < (a^2+b^2)*r0^2
is reasonably cheap (4 multiplications and 2 additions) assuming that r0^2 and (a^2+b^2) is precomputed. You may have to be careful about overflows.
With modern GFLOP processors, you can test a lot of circles in real time. It all depends on how many circles you have and how they are organised.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Hi,
this is great, and mathematically correct.
When all coordinates use no more than 14 bits (that is 16000 pixels), then everything
can be calculated in 32-bit signed integer arithmetic without risking overflows.
Seems much better than the sorted-squares stuff...
|
|
|
|
|
Hmm… I'd have to agree that dividing MAP into regions would be horribly complex (I haven't even implemented the code yet), but then again, I'm restricted to floating-point math, so I can't take the integer math approach. I'm also quite skeptical about testing every circle. Maybe I should make it more scalable, and allow automatic selection of algorithms based on certain conditions.
In the end, we converge towards an optimal solution, but we never reach it.
ROFLOLMFAO
|
|
|
|
|
Hi,
some more thoughts:
1. Whatever was said about integers can be done in float as well.
2. how many circles are there ? thousands ? and how many times per second
do you need the hit testing ? a modern CPU executes 1 billion instr/sec !
3. in my experience, reflecting before implementing is good (it allows for
wise initial choices), but optimizing things that dont exist yet is not;
optimization must be based on observations and measurements.
Good luck !
|
|
|
|
|
I'll take every idea into consideration. It is a testing platform for a bigger project after all, and a better idea can't be ignored!
Thank you for all your input! 
ROFLOLMFAO
|
|
|
|
|
Thanks. I'm guessing this goes back to the "l × c"* approach — comparing every line with every circle. If that turns out to be faster, I'll implement that too (you gotta love interfaces and virtual methods!).
By the way, everything is done using the Double type. (It's the type that Windows Presentation Foundation works with.)
* Represents the number of comparisons that needs to be made based on the number of lines and circles. The number of lines never exceeds the number of circles, so a lower bound would be 0 tests for no activity, and Math.Pow(c, 2) for the upper bound (when everyone is firing their uzis at once).
ROFLOLMFAO
|
|
|
|
|
If a line intersects a circle then it also intersects a square centered at the same location and with a side length equal to the diameter of the circle. That fact could be use as the first stage in your hit detection.
Steve
|
|
|
|
|
I can't see how to test for intersection with a square that is cheaper than testing for intersection with a circle. The best methods I can come up with are actually harder to test with a square than a circle.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
I haven't seen the algorithms being used but I don't find it hard to imagine that an algorithm based on the Cohen-Sutherland line clipping algorithm, for example, could speed things up. Also lines of code need not mean slower code.
Steve
|
|
|
|
|
Thanks for the link Steve - now I see where you are coming from. Guess there is no right answer (particularly without knowing all the problem), for finite line segments algorithms like you propose may be the best (although the answer will depend on the level of hardware support available), for infinite line segments the simple testing earlier in the thread could be promising. This looks like a semi-infinite problem so maybe a combination will turn out to be the best.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
I've never done any gaming programming, so my idea may be way off, but...
I assume that the circles are objects that maintain data about themselves. Could you have the circle objects keep track of what ray would intersect them? That way all the calculations would be done at the time of movement, and at the time the gun is fired, all that needs to be done is to check each circle to see if the shot qualifies as a hit.
Roy.
|
|
|
|
|
Hum. Thats an interesting approach. It helps the animation effect for sure,
but to apply this in a WPF context ?
And what if there are other kinds of objects around ? Bullets hitting each other ?
Walls being hit ? (well, if this matters it needs a solution anyhow).
|
|
|
|
|
How can I use Runge Kutta algorithm to programme a fractal?
Noha.Y
|
|
|
|
|
long time ago I used Runga-Kutta for numerical integration.
I dont see the use/need for it in fractals...
|
|
|
|
|
The use of runge kutta method is for dynamical systems, and fractals are dynamical systems..
My question now is: how did you use Runga Kutta for numerical integration?
Noha.Y
|
|
|
|
|
I once wrote a simulator for electronic circuits (a precursor of Spice);
using Fortran, the high-level language at that time.
for "time analysis" one has to cope with the intgerating effect of capacitors
and inductors; this is where different integration techniques can be useful,
e.g. Runge-Kutta.
You can find more on RK through Google, for instance here[^]
|
|
|
|
|
Thank you very much 
It helped me!
But what if I want to write a program??
|
|
|
|
|
Hi Luc,
I used Spice in college. Are you an author?
Jeff
|
|
|
|
|
No I am not an author of Spice, I met some of its authors when visiting Berkeley
University tho. And I participated in the development of similar programs in
Belgium, and did one myself. At that time SPICE (SPICE 1 that is) missed several
features that we needed badly, mostly in frequency analysis(poles and zeroes,
impedance calculation, S-parameters ...).
|
|
|
|
|
RK is used for approximating solutions to differential equations, which don't really have anything to do with fractals.
Do you have any particular reason to try and program something using Runge-Kutta or fractals? If you explain what you want to do a bit better, I might be able to point you in the right direction.
|
|
|
|
|
OK.. Can you give your email to send for you the mission I have to do?
Mine is: noha.yassin@gmail.com
Thanks
Noha.Y
|
|
|
|
|
i wish to learn about timetabling problem. From the surface, it does look quite easy to understand. but i don't really understand how does algorithm such as GA/SA/ACO can solve the problem? I mean, how to apply those algorithm into the problem?
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
