How to use diagonal Collision Detection

Content and general development discussion, including maps, quests, and server code from the development team.
Post Reply
User avatar
Seradest
Novice
Novice
Posts: 169
Joined: 04 Mar 2009, 03:22

How to use diagonal Collision Detection

Post by Seradest » 28 Mar 2009, 01:09

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.
zick
Novice
Novice
Posts: 194
Joined: 21 Feb 2007, 04:30
Location: City Of Champions Again

Re: How to use diagonal Collision Detection

Post by zick » 03 Apr 2009, 02:46

Are you talking about isometric view?
User avatar
Seradest
Novice
Novice
Posts: 169
Joined: 04 Mar 2009, 03:22

Re: How to use diagonal Collision Detection

Post by Seradest » 03 Apr 2009, 14:32

zick wrote:Are you talking about isometric view?
No

i think the devs know what i mean.
User avatar
Crush
TMW Adviser
TMW Adviser
Posts: 8046
Joined: 25 Aug 2005, 17:08
Location: Germany

Re: How to use diagonal Collision Detection

Post by Crush » 03 Apr 2009, 15:39

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.
  • former Manasource Programmer
  • former TMW Pixel artist
  • NOT a game master

Please do not send me any inquiries regarding player accounts on TMW.


You might have heard a certain rumor about me. This rumor is completely false. You might also have heard the other rumor about me. This rumor is 100% accurate.
User avatar
Jaxad0127
TMW Adviser
TMW Adviser
Posts: 4209
Joined: 01 Nov 2007, 18:35
Location: Internet

Re: How to use diagonal Collision Detection

Post by Jaxad0127 » 03 Apr 2009, 16:03

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).
Image
User avatar
Crush
TMW Adviser
TMW Adviser
Posts: 8046
Joined: 25 Aug 2005, 17:08
Location: Germany

Re: How to use diagonal Collision Detection

Post by Crush » 03 Apr 2009, 16:06

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.
  • former Manasource Programmer
  • former TMW Pixel artist
  • NOT a game master

Please do not send me any inquiries regarding player accounts on TMW.


You might have heard a certain rumor about me. This rumor is completely false. You might also have heard the other rumor about me. This rumor is 100% accurate.
User avatar
Jaxad0127
TMW Adviser
TMW Adviser
Posts: 4209
Joined: 01 Nov 2007, 18:35
Location: Internet

Re: How to use diagonal Collision Detection

Post by Jaxad0127 » 03 Apr 2009, 16:19

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?
Image
User avatar
Seradest
Novice
Novice
Posts: 169
Joined: 04 Mar 2009, 03:22

Re: How to use diagonal Collision Detection

Post by Seradest » 03 Apr 2009, 16:25

User avatar
Crush
TMW Adviser
TMW Adviser
Posts: 8046
Joined: 25 Aug 2005, 17:08
Location: Germany

Re: How to use diagonal Collision Detection

Post by Crush » 03 Apr 2009, 17:46

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".
  • former Manasource Programmer
  • former TMW Pixel artist
  • NOT a game master

Please do not send me any inquiries regarding player accounts on TMW.


You might have heard a certain rumor about me. This rumor is completely false. You might also have heard the other rumor about me. This rumor is 100% accurate.
User avatar
Kage
Warrior
Warrior
Posts: 927
Joined: 02 May 2009, 19:12

Re: How to use diagonal Collision Detection

Post by Kage » 29 May 2009, 18:20

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.
<Kage_Jittai> ... are you saying I am elite :D
<thorbjorn> Yes. :P
User avatar
Jaxad0127
TMW Adviser
TMW Adviser
Posts: 4209
Joined: 01 Nov 2007, 18:35
Location: Internet

Re: How to use diagonal Collision Detection

Post by Jaxad0127 » 29 May 2009, 18:26

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.
Image
Post Reply