Move range searching

Post those lines of code you feel like sharing or find what you require for your project here; or simply use them as tutorials.
Post Reply
Vandal
Posts: 14
Joined: Fri Jun 12, 2009 3:44 am

Move range searching

Post by Vandal »

I am thinking how to search the range a character can move now. I made a sample program, so I expose.
Look at pictures. "S" is a start point, brown squares are walls and cyan ones are floors, and each number signifies move power left for shift -- the search process stops when the move power is exhausted. Green ones are the woods, and two move powers are used there. Pink is a route.
Those pictures were drawn by Irrlicht.

Binary
http://www.mediafire.com/download.php?jxyzjtyttkh

Image
Image
Image
Last edited by Vandal on Tue Feb 16, 2010 10:19 am, edited 2 times in total.
hybrid
Admin
Posts: 14143
Joined: Wed Apr 19, 2006 9:20 pm
Location: Oldenburg(Oldb), Germany
Contact:

Post by hybrid »

Do you have any code, or at least some description about how you create the levels/search results?
This isn't really a project, so I'll move it to code snippets - you just have to add the code therefore.
trivtn
Posts: 132
Joined: Tue Jan 17, 2006 12:30 pm
Location: Viet Nam
Contact:

Post by trivtn »

I've use bitmap file as the Map of finding. An average value as the searching value ( <64 is no moving into).
There's something is fantastic, there's nothing is absolute.
Vandal
Posts: 14
Joined: Fri Jun 12, 2009 3:44 am

A*

Post by Vandal »

I tried searching move range by "A*", and succeeded. This is a very simple program for testing, and I must coordinate it for common game usage. Needless to say, this program is necessary to characters' moving of various games.

Image
Image
Image
Virion
Competition winner
Posts: 2148
Joined: Mon Dec 18, 2006 5:04 am

Post by Virion »

i'm not a tech guy here but normally if let say I am S and I'm going after F, wouldn't I go straight to him rather than walking along the sideway? Since there isn't any obstacle in the middle. just my 2 cents though.

Image
ErUs
Posts: 165
Joined: Thu Oct 07, 2004 6:13 pm

Post by ErUs »

Virion wrote:i'm not a tech guy here but normally if let say I am S and I'm going after F, wouldn't I go straight to him rather than walking along the sideway? Since there isn't any obstacle in the middle. just my 2 cents though.
Same distance, but like you say; i think most games will try to zig-zag.
This could be done by keeping a record of last move direction, then if you have an equal cost of moving in 2 directions try not to move in the same one as the last time.
Acki
Posts: 3496
Joined: Tue Jun 29, 2004 12:04 am
Location: Nobody's Place (Venlo NL)
Contact:

Post by Acki »

Virion wrote:i'm not a tech guy here but normally if let say I am S and I'm going after F, wouldn't I go straight to him rather than walking along the sideway? Since there isn't any obstacle in the middle. just my 2 cents though.
no, if you look at this picture:
Image
you'll see that each square has a moving range value...
and if you count the values you'll see the (long) path has a lesser value than the streight path... ;)
(at least this how I understand this :lol: )
while(!asleep) sheep++;
IrrExtensions:Image
http://abusoft.g0dsoft.com
try Stendhal a MORPG written in Java
hybrid
Admin
Posts: 14143
Joined: Wed Apr 19, 2006 9:20 pm
Location: Oldenburg(Oldb), Germany
Contact:

Post by hybrid »

No, that version was probably the completely clear version. But as ErUs said, both ways are the same distance (as we're not in euklidian space anymore) and hence are equally good. So it depends on side conditions or the search order which path is found.
Ulf
Posts: 281
Joined: Mon Jun 15, 2009 8:53 am
Location: Australia

Post by Ulf »

He's talking about weighted graphs. Each node has it's own weight.

But the example he gave, both paths add up to 6
I can hear birds chirping
:twisted:

I live in the Eye of Insanity.
Acki
Posts: 3496
Joined: Tue Jun 29, 2004 12:04 am
Location: Nobody's Place (Venlo NL)
Contact:

Post by Acki »

Ulf wrote:Each node has it's own weight.
..., that's what I meant with "moving range value" !!! :lol:
while(!asleep) sheep++;
IrrExtensions:Image
http://abusoft.g0dsoft.com
try Stendhal a MORPG written in Java
Vandal
Posts: 14
Joined: Fri Jun 12, 2009 3:44 am

Post by Vandal »

Virion, your point that it seems more natural that a character trads zigazag is correct, but zigzag will increase useless actions --waste time for turn-- in the project I am imaging. I let a man walk as straight as possible.
The first, second, and third pictures are not A*. They are calculated only by a move value each square has without A*. All a* programs have window-titles "A*". :wink:
Vandal
Posts: 14
Joined: Fri Jun 12, 2009 3:44 am

Post by Vandal »

This is a sample that I extended my A* program to 3D. It is so easy to apply a complete program on Irrlicht to 3D.

Demo
http://www.mediafire.com/download.php?mzzojwgkuo2

Image[/url]
Last edited by Vandal on Fri Feb 19, 2010 10:13 pm, edited 1 time in total.
Virion
Competition winner
Posts: 2148
Joined: Mon Dec 18, 2006 5:04 am

Post by Virion »

Vandal wrote:This is a sample that I extended my A* program to 3D. It is so easy to apply a complete program on Irrlicht to 3D.

Image
looks good! hope to see a 3d model running on the path soon!
Post Reply