Calculating path to take

9b9aa8d8eaa23f61fdaf6dbb624b5011
0
Orias 101 Oct 26, 2008 at 23:32

Hi there,

I’m new here, and I need some help! I haven’t programmed artifical intelligence for very long, but am trying my hands at developing a “Heroes of Might and Magic”-type of game. I have made the basic 2d engine, and have begun to create the battle systems. This is a screen of how the battlescreen looks so far (easier to show you, than to explain how it looks): http://www.orias.se/bfield.jpg. Now, what I want to do, is come up with a way for the currently selected unit, to be able to walk anywhere on the map, in a streight line, but only through the grids, and not “birds”-way. Anyone who have played Heroes of Might and Magic 2 or 3 knows what I mean.
My first instinct was to take the destination x position minus the start x position divided by the destination y position minus the starting y position, or rather:

(destX - startX) / (destY - startY)

and then transform it into an integer (this was done for when moving anywhere from east to south)

This is the code I came up with (I am using Blitz3D as my programming
language - and sorry for no tabs etc, but the website didn’t seem to
have a tag, or at least it didn’t work for me): ; Create a movement path
for the unit. Function createUnitMovementPath(mode) Local lengthX :
Local startX : Local destX : Local currentX Local lengthY : Local startY
Local destY : Local currentY Local ammountOfXBeforeYChange : Local currentGridCount Local ammountOfYBeforeXChange : Local totalGridCount ; Reset the movement tag. movementTag = 0 ; Get the starting position. If creatureOrder[turnCountBF] < 8 Then startX = monsters(currentTurnBF,creatureOrder[turnCountBF],19) startY = monsters(currentTurnBF,creatureOrder[turnCountBF],20) Else If creatureOrder[turnCountBF] > 7 Then startX = monsters(currentTurnBF,creatureOrder[turnCountBF] - 7,19) startY = monsters(currentTurnBF,creatureOrder[turnCountBF] - 7,20) End If ; Set the destination. destX = posXGridBF destY = posYGridBF ; Set how many grids it’s gonna move. lengthX = destX - startX + 1 lengthY = destY - startY + 1 lengthX = lengthX - (lengthX Mod lengthY) lengthY = lengthY - (lengthY Mod lengthY) ; These calculate how many x grids to go before you change y, or ; how many y grids to go before you change x. ammountOfXBeforeYChange = lengthX / lengthY ammountOfYBeforeXChange = lengthY / lengthX ammountOfXBeforeYChange = Int(ammountOfXBeforeYChange) ammountOfYBeforeXChange = Int(ammountOfYBeforeXChange) ; This create the actual path. currentGridCount = 0 totalGridCount = lengthX + lengthY ; Set the starting position. movementPath(0,0) = startX movementPath(0,1) = startY ; Set the movement path. If ammountOfXBeforeYChange >= ammountOfYBeforeXChange Then For y = 1 To lengthY For x = 1 To ammountOfXBeforeYChange movementPath(currentGridCount,0) = startX + currentX movementPath(currentGridCount,1) = startY + currentY currentGridCount = currentGridCount + 1 currentX = currentX + 1 Next currentY = currentY + 1 Next Else If ammountOfXBeforeYChange < ammountOfYBeforeXChange Then For x = 1 To lengthX For y = 1 To ammountOfYBeforeXChange movementPath(currentGridCount,0) = startX + currentX movementPath(currentGridCount,1) = startY + currentY currentGridCount = currentGridCount + 1 currentY = currentY + 1 Next currentX = currentX + 1 Next End If ; Make sure there’s an end to the movement path. If mode = 0 Then movementPath(currentGridCount,0) = 999 movementPath(currentGridCount,1) = 999 Else If mode = 1 Then movementPath(currentGridCount,0) = 666 movementPath(currentGridCount,1) = 666 End If End Function ; Move a creature (unit) to a specific grid position on the battlefield, ; if possible, and animate it. Function moveUnit() ; Set the current position of the unit. currentXPosBF = movementPath(movementTag,0) currentYPosBF = movementPath(movementTag,1) ; Raise the movement tag. movementTag = movementTag + 1 ; Check if the unit has reached its final destination. If movementPath(movementTag,0) = 666 Or movementPath(movementTag,1) = 666 Then battleCommand = “checkAttack” Delay 500 Else If movementPath(movementTag,0) = 999 Or movementPath(movementTag,1) = 999 Then battleCommand = “endTurn” End If ; Draw the unit (aka creature) at it’s correct position. If creatureOrder[turnCountBF] < 8 Then monsters(currentTurnBF,creatureOrder[turnCountBF],19) = currentXPosBF monsters(currentTurnBF,creatureOrder[turnCountBF],20) = currentYPosBF Else If creatureOrder[turnCountBF] > 7 Then monsters(currentTurnBF,creatureOrder[turnCountBF] - 7,19) = currentXPosBF monsters(currentTurnBF,creatureOrder[turnCountBF] - 7,20) = currentYPosBF End If Delay 100 End Function If the code is not clear enough, I can clear things up for ya, but you’ll have to ask. Please help me with this. I am stuck :) Regards, Anton [code] tag, or at least it didn’t work for me):

; Create a movement path for the unit.
Function createUnitMovementPath(mode)
Local lengthX : Local startX : Local destX : Local currentX
Local lengthY : Local startY : Local destY : Local currentY

Local ammountOfXBeforeYChange : Local currentGridCount
Local ammountOfYBeforeXChange : Local totalGridCount

; Reset the movement tag.
movementTag = 0

; Get the starting position.
If creatureOrder[turnCountBF] < 8 Then
startX = monsters(currentTurnBF,creatureOrder[turnCountBF],19)
startY = monsters(currentTurnBF,creatureOrder[turnCountBF],20)
Else If creatureOrder[turnCountBF] > 7 Then
startX = monsters(currentTurnBF,creatureOrder[turnCountBF] - 7,19)
startY = monsters(currentTurnBF,creatureOrder[turnCountBF] - 7,20)
End If

; Set the destination.
destX = posXGridBF
destY = posYGridBF

; Set how many grids it’s gonna move.
lengthX = destX - startX + 1
lengthY = destY - startY + 1
lengthX = lengthX - (lengthX Mod lengthY)
lengthY = lengthY - (lengthY Mod lengthY)

; These calculate how many x grids to go before you change y, or
; how many y grids to go before you change x.
ammountOfXBeforeYChange = lengthX / lengthY
ammountOfYBeforeXChange = lengthY / lengthX
ammountOfXBeforeYChange = Int(ammountOfXBeforeYChange)
ammountOfYBeforeXChange = Int(ammountOfYBeforeXChange)

; This create the actual path.
currentGridCount = 0
totalGridCount = lengthX + lengthY

; Set the starting position.
movementPath(0,0) = startX
movementPath(0,1) = startY

; Set the movement path.
If ammountOfXBeforeYChange >= ammountOfYBeforeXChange Then
For y = 1 To lengthY
For x = 1 To ammountOfXBeforeYChange
movementPath(currentGridCount,0) = startX + currentX
movementPath(currentGridCount,1) = startY + currentY
currentGridCount = currentGridCount + 1
currentX = currentX + 1
Next
currentY = currentY + 1
Next
Else If ammountOfXBeforeYChange < ammountOfYBeforeXChange Then
For x = 1 To lengthX
For y = 1 To ammountOfYBeforeXChange
movementPath(currentGridCount,0) = startX + currentX
movementPath(currentGridCount,1) = startY + currentY
currentGridCount = currentGridCount + 1
currentY = currentY + 1
Next
currentX = currentX + 1
Next
End If

; Make sure there’s an end to the movement path.
If mode = 0 Then
movementPath(currentGridCount,0) = 999
movementPath(currentGridCount,1) = 999
Else If mode = 1 Then
movementPath(currentGridCount,0) = 666
movementPath(currentGridCount,1) = 666
End If
End Function

; Move a creature (unit) to a specific grid position on the battlefield,
; if possible, and animate it.
Function moveUnit()
; Set the current position of the unit.
currentXPosBF = movementPath(movementTag,0)
currentYPosBF = movementPath(movementTag,1)

; Raise the movement tag.
movementTag = movementTag + 1

; Check if the unit has reached its final destination.
If movementPath(movementTag,0) = 666 Or movementPath(movementTag,1) = 666 Then
battleCommand = “checkAttack”
Delay 500
Else If movementPath(movementTag,0) = 999 Or movementPath(movementTag,1) = 999 Then
battleCommand = “endTurn”
End If

; Draw the unit (aka creature) at it’s correct position.
If creatureOrder[turnCountBF] < 8 Then
monsters(currentTurnBF,creatureOrder[turnCountBF],19) = currentXPosBF
monsters(currentTurnBF,creatureOrder[turnCountBF],20) = currentYPosBF
Else If creatureOrder[turnCountBF] > 7 Then
monsters(currentTurnBF,creatureOrder[turnCountBF] - 7,19) = currentXPosBF
monsters(currentTurnBF,creatureOrder[turnCountBF] - 7,20) = currentYPosBF
End If

Delay 100
End Function

If the code is not clear enough, I can clear things up for ya, but you’ll have to ask. Please help me with this. I am stuck :)

Regards,
Anton

2 Replies

Please log in or register to post a reply.

A638aa42130293f319eda7fa4ba121f4
0
fireside 141 Oct 27, 2008 at 00:23

Usually you use A* (A star) path finding for that. It’s looks like you’ve done some work there, so I don’t know. You might want to at least do a search and check it out.

9b9aa8d8eaa23f61fdaf6dbb624b5011
0
Orias 101 Oct 27, 2008 at 03:57

@fireside

Usually you use A* (A star) path finding for that. It’s looks like you’ve done some work there, so I don’t know. You might want to at least do a search and check it out.

Thanks alot! :) Just what I needed!