|
Calculate distance in a board game
#172068
12/10/07 16:38
12/10/07 16:38
|
Joined: Oct 2004
Posts: 290 Latvia
Leonardo
OP
Member
|
OP
Member
Joined: Oct 2004
Posts: 290
Latvia
|
Hi! I am writing a board game AI, that moves and attacks the player's pieces. Let's say I have a board that is 8x8 squares large and I need to calculate the shortest distance from one square to another, keeping in mind that some of the squares in the path cannot be used, because they are full, so the AI player needs to get around these squares. Anything is appreciated - ranging from simple ideas to full pieces of c-script code. Oh, another thing - it would be good if someone could explain to me how to do this using nodes. Leonardo
"Things of the mind left untested by the senses are useless."
|
|
|
Re: Calculate distance in a board game
[Re: mk_1]
#172070
12/11/07 04:56
12/11/07 04:56
|
Joined: Jan 2006
Posts: 968
EpsiloN
User
|
User
Joined: Jan 2006
Posts: 968
|
The Manhattan distance Quote:
H can be estimated in a variety of ways. The method we use here is called the Manhattan method, where you calculate the total number of squares moved horizontally and vertically to reach the target square from the current square, ignoring diagonal movement, and ignoring any obstacles that may be in the way. We then multiply the total by 10, our cost for moving one square horizontally or vertically.
Reading this description, you might guess that the heuristic is merely a rough estimate of the remaining distance between the current square and the target "as the crow flies." This isn't the case. We are actually trying to estimate the remaining distance along the path (which is usually farther). The closer our estimate is to the actual remaining distance, the faster the algorithm will be. If we overestimate this distance, however, it is not guaranteed to give us the shortest path. In such cases, we have what is called an "inadmissible heuristic."
Technically, in this example, the Manhattan method is inadmissible because it slightly overestimates the remaining distance. But we will use it anyway because it is a lot easier to understand for our purposes, and because it is only a slight overestimation. On the rare occasion when the resulting path is not the shortest possible, it will be nearly as short. Want to know more? You can find equations and additional notes on heuristics here.
Source : http://www.igda.org/Forums/showthread.php?threadid=22955 (But thats not the original tutorial, I dont have time to find it right now and btw , there was a whole section in a site , I forgot it , but there was an explanation to many ways of calculating distance to a target square )
|
|
|
Re: Calculate distance in a board game
[Re: Leonardo]
#172071
12/11/07 16:05
12/11/07 16:05
|
Joined: Dec 2000
Posts: 4,608
mk_1
Expert
|
Expert
Joined: Dec 2000
Posts: 4,608
|
Quote:
<...>keeping in mind that some of the squares in the path cannot be used, because they are full, so the AI player needs to get around these squares.
Manhattan distance doesn't work here.
|
|
|
Re: Calculate distance in a board game
[Re: mk_1]
#172072
12/11/07 19:38
12/11/07 19:38
|
Joined: Jan 2006
Posts: 968
EpsiloN
User
|
User
Joined: Jan 2006
Posts: 968
|
Quote:
ignoring any obstacles that may be in the way
Thats for the pathfinding to 'check'
|
|
|
|