Page 1 of 1

How to use diagonal Collision Detection

Posted: 28 Mar 2009, 01:09
by Seradest
Here examples
http://www.allegro.cc/forums/thread/192885/193200
http://www.palib.info/wiki/doku.php?id= ... ion_theory
http://entity.ummu.umich.edu/~wsoft/article.php?id=14
http://compsci.ca/v3/viewtopic.php?p=144593

I hope i a diiiiiiiiiiiiiiiiiiiiiiiiiiistaaaaaaaaaaaaaaaaand Future we have it...... no chessboard vegetation animore.

Re: How to use diagonal Collision Detection

Posted: 03 Apr 2009, 02:46
by zick
Are you talking about isometric view?

Re: How to use diagonal Collision Detection

Posted: 03 Apr 2009, 14:32
by Seradest
zick wrote:Are you talking about isometric view?
No

i think the devs know what i mean.

Re: How to use diagonal Collision Detection

Posted: 03 Apr 2009, 15:39
by Crush
First: It is very unlikely that we will have anything but binary per-tile movement on eAthena. Thus all attempts for better movement must be TMWServ-based.


The biggest problem we have with pixel-accurate movement on tmwserv is not the collision detection. Programming collision detection checks is trivial for any programmer who completed high school geometry (when it is not supposed to be fast, at least). Our problem is the pathfinding.

We are using A* for pathfinding which works pretty well when an object covers one unit but does not work when an object covers multiple units. We also can not use A* on pixels instead of tiles because it would increase the map size (from the point of view of the algorithmn) from a few hundred steps to a few thousand steps. This would be impossible to handle because of memory consumption and CPU time. Thus the route finding and path blocking does still work on a per-tile base which leads to awkward movement.

An algorithmn based on BSP or a Quadtree might be the direction to look into.

Re: How to use diagonal Collision Detection

Posted: 03 Apr 2009, 16:03
by Jaxad0127
Crush wrote:First: It is very unlikely that we will have anything but binary per-tile movement on eAthena.
Subtile eAthena placement would work (instead of each map tile being one placement tile, it would be four, or eight).

Re: How to use diagonal Collision Detection

Posted: 03 Apr 2009, 16:06
by Crush
But then you would also have to live with every object only covering one subtile portion because A* can not handle a walker which needs more than one node of space.

Re: How to use diagonal Collision Detection

Posted: 03 Apr 2009, 16:19
by Jaxad0127
Crush wrote:But then you would also have to live with every object only covering one subtile portion because A* can not handle a walker which needs more than one node of space.
You're looking at replacing A* anyways...or is that an eAthena limit?

Re: How to use diagonal Collision Detection

Posted: 03 Apr 2009, 16:25
by Seradest

Re: How to use diagonal Collision Detection

Posted: 03 Apr 2009, 17:46
by Crush
jaxad0127 wrote:You're looking at replacing A* anyways...or is that an eAthena limit?
A* is used internally by eAthena. A replacement for A* is what I am talking about, at the moment.
Here PERFECT PATHFINDING
I'm sorry, but you are not a programmer, Seradest. I know, you just want to help, but unfortunately you lack the expertise in this area to be really helpful. You should leave finding a solution to the people who actually understand the problems.

The links you are posting could be compared to going to the doctor with an anatomy handbook in your hand and saying "I am sure somewhere in there is a way to heal me".

Re: How to use diagonal Collision Detection

Posted: 29 May 2009, 18:20
by Kage
I have noticed a few difference between ours and eA implementation of A*

But non the less, the client should be using the exact same algorithm as the server.

Re: How to use diagonal Collision Detection

Posted: 29 May 2009, 18:26
by Jaxad0127
Kage wrote:I have noticed a few difference between ours and eA implementation of A*

But non the less, the client should be using the exact same algorithm as the server.
Yes. It causes lots of player frustration and visual errors.