Movement Algorithm
Annamma Alexander
crawl type game.The entire dungeon was to be a char array with each
element representing a tile(walls,water,doors etc.) Things went
reasonably smoothly until I crashed headfirst into the movement
algorithm for my monsters. The specific situation is as below:
P
------------------
| |
| M |
| |
|
|________|
_ | --- represent walls
M ---- our stoopid (albeit evil) monster
P ---- the helpless player
Can anyone figure out the logic for the monster to find his way to the
player's sqaure? The problem that stumps me that the monster has to
move _AWAY_ from the player to exit the room and then _TOWARDS_
the player once it leaves the room?
Any help would be really
appreciated --- :)
aale...@wwonline.com
gil
are in the same room; if player and monster are in two different rooms, look
for a path in terms of rooms (can be a tree) them move your monster from
room to room, and when your monster is in same room as player's use your
MoClToPlayer() function.
Cheers.
Gil
Orson Scott Card, Robert Sheckley, Robert Heinlein,Racine,Mendel Mann,Ernst Lubitch, thanks a lot.
ss...@intranet.ca
Subject: Movement Algorithm
This is getting sad. We really need a FAQ. I'm *this* (Sunir holds fingers
apart as far as he possibly can) close to getting fed up enough to do it. :)
[No offense, Annamma 'Tis just a frequently asked question :)]
As I just wrote to a certain other unnamed person in private e-mail:
What you described is called intelligent unit navigation, or the shortest path
algorithm (SPA).
These are links to the same pages. It seems to bounce between these two URLs
so try both of them:
http://www.himolde.no/~lonning/shorpath.htm
http://www.lis.pitt.edu/~john/shorpath.htm
[More specific reply:]
Aa> P
Aa> ------------------
Aa> | |
Aa> | M |
Aa> | |
Aa> |
Aa> |________|
Aa>
Aa> _ | --- represent walls
Aa> M ---- our stoopid (albeit evil) monster
Aa> P ---- the helpless player
Aa> Can anyone figure out the logic for the monster to find his way to the
Aa> player's sqaure? The problem that stumps me that the monster has to
Check out the web pages I listed above.
Aa> move _AWAY_ from the player to exit the room and then _TOWARDS_
Aa> the player once it leaves the room?
Why? There's a shorter path to go left. If that wall was closed off, then
yes, the monster would have to go away from the player first because there is
no other way out of the room.
--
Sunir Shah (ss...@intranet.ca) http://intranet.ca/~sshah/
BBS: The Open Fire BBS +1(613)584-1606 Fidonet: 1:241/11
The Programmers' Booklist : http://intranet.ca/~sshah/booklist.html
Synapsis Entertainment : http://intranet.ca/~sshah/synapsis.html
WASTE (Wargame AI Contest): http://intranet.ca/~sshah/waste/waste.html
___ Blue Wave/QWK v2.12
>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED
Bjorn Reese
> Can anyone figure out the logic for the monster to find his way to the
> player's sqaure? The problem that stumps me that the monster has to
> move _AWAY_ from the player to exit the room and then _TOWARDS_
> the player once it leaves the room?
This is not a trivial issue. I suggest that you'll look at how
navigation and planning are handled in robotics. A good introduction
is
McKerrow, Phillip John
"Introduction to Robotics"
Addison-Wesley, 1991
ISBN 0-201-18240-8
--
Bjorn Reese Email: bre...@imada.ou.dk
Odense University, Denmark URL: http://www.imada.ou.dk/~breese
"It's getting late in the game to show any pride or shame" - Marillion
Tom Dawson
>I recently embarked on a project to make an overhead view dungeon
>crawl type game.The entire dungeon was to be a char array with each
>element representing a tile(walls,water,doors etc.) Things went
>reasonably smoothly until I crashed headfirst into the movement
>algorithm for my monsters. The specific situation is as below:
>
> P
>
> ------------------
> | |
> | M |
> | |
> |
> |________|
>
>
>_ | --- represent walls
>
>
>
>player's sqaure? The problem that stumps me that the monster has to
>move _AWAY_ from the player to exit the room and then _TOWARDS_
>the player once it leaves the room?
A simple solution (not the best, but many older games do this)
If there is a wall between you monster and the player, have it move in a
random direction. If it has a clear path, move it towards the player. The
monster will bounce around in the room for a while and will eventually
bounce out of the room. Another trick is to know when you are in a hallway
rather than a "room" and bias the hallway random moves toward the players
position.
You could map all the paths between all the rooms but that can get big
fast for a decent number of rooms.
The bounce around technique works ok and doesn't use up memory with path
data between all the rooms.
Have fun
Tom
Tim Hardy
You want to do this right - not some hacked up job. I think other
people have posted sites for these algorithms, and I have looked at
them all. If you look at the thread I started "Best Path Algorithm",
you'll find that I took C source code for A* (a good algorithm) off of
one of those sites and converted it to C++. I posted most of my
source fragments in that thread, but I am in the process of optimizing
it and trying to get other people to help me speed it up. When I am
done, I will probably make my final code available.
The guy who mentioned the faq is absolutely right. We need to have
all this stuff in a faq. There is enough info on the net to put the
following in a faq:
Topic: Shortest Path
Solutions:
A* Algorithm
Description:
blah, blah, blah.
Source Code:
C++:
source code here
C:
source code here
Pascal:
source code here
Dijkstra's Algorithm:
Same stuff for Dijkstra's.
Topic: Scrolling
etc.
etc.
etc.
This would eliminate half of the posts for rec.games.programmer and
comp.ai.games.
I will volunteer the C++ A* code (MSVC 2.2 - using MFC) if anyone
wants to do the faq.
Tim
IG. Badcoe
Handle movement between rooms differently from movement within rooms.
For between rooms just keep a note of which rooms are in contact and where
the connections are then you can use a 'finite diffusion' method (or a
brute force search if thewre are few enough rooms) to calculate the series
of rooms through which the monster must pass.
We've discussed this in great detail on this group in the past.
Look in the FAQ and consult the archives.
Badders
Steven Woodcock
: The guy who mentioned the faq is absolutely right. We need to have
: all this stuff in a faq. There is enough info on the net to put the
: following in a faq:
: Topic: Shortest Path
: Solutions:
: A* Algorithm
: Description:
: blah, blah, blah.
: Source Code:
: C++:
: source code here
: C:
: source code here
: Pascal:
: source code here
: Dijkstra's Algorithm:
: Same stuff for Dijkstra's.
: Topic: Scrolling
: etc.
: etc.
: etc.
: This would eliminate half of the posts for rec.games.programmer and
: comp.ai.games.
We had a FAQ that was much like that. It died when the maintainer
found other things to do (I think his machine died).
A FAQ would be cool to have but I'd just like to point out that
when we *did* have it it really didn't cut down on duplicate problem
requests like this one. It's a common problem.
But, if we want to do one again I'll help.
Steve
+=============================================================================+
| _ |
| Steven Woodcock _____C .._. |
| Senior Software Engineer, Gameware ____/ \___/ |
| Lockheed Martin Information Systems Group <____/\_---\_\ "Ferretman" |
| Phone: 719-597-5413 |
| E-mail: wood...@escmail.orl.mmc.com (Work), swoo...@cris.com (Home) |
| Web: http://www.cris.com/~swoodcoc/wyrdhaven.html (Top level page) |
| http://www.cris.com/~swoodcoc/ai.html (Game AI page) |
| Disclaimer: My opinions in NO way reflect the opinions of |
| the Lockheed Martin Information Systems Group |
+=============================================================================+
Steve
writeth:
> A FAQ would be cool to have but I'd just like to point out that
>when we *did* have it it really didn't cut down on duplicate problem
>requests like this one. It's a common problem.
It may not cut down on request, but it would make replies easier. Instead of
'blahblahblahmoveleftblahrepulsiveforceblahfuzzylogicblah' you could just say
'RTFAQ' and if they still don't understand then you help them.
I'm still looking for somebody to give me a movement algorithm that I can
understand (I have imense trouble understanding sombody elses code unless I have
an english translation)
-Steve
------------------------------------------------------------
__ ,' ,. ,,
\,''-.., ,'' .,.', ', ,', .,','
_-''-. ''-,'_.' ' ',,' ', ,' ,',
) ) -*\ 'O, ,' ,',', ', ',, ,
) ) /,..,,.,-,.,' ,.,' .,' ''.,' ,'
@_.,.) >-,._, ''.'--,''''' ,' ,,
' '''-,,_ '-,, -,., ,' ','
.'''._' '-,..,.,. ,',_....,'
',/' ''.,,,..,.,,.-''
Ye Olde Dragon Of Ask'eeyart. Now kneel or else.
------------------------------------------------------------