[Game]Laufen in alle Richtungen auf einem 2d-Raster?

[Phelot]

Hey :>

Also, ich bringe mir hier eben selber Python bei und experimentiere ein wenig mit pygame, einem toolkit um Spiele zu machen.
Die Idee ist irgendwann mal einen simplen topview Diablo2-PVP-Klon zu machen, in dem man laufen, herumteleportieren und Feuerbälle schiessen kann.
Das Problem ist eigentlich ziemlich generell und hat vermutlich nicht speziell etwas mit Python/pygame zu tun, also könnte mir hier vielleicht jemand helfen, der eigentlich keine Erfahrung mit dem toolkit hat.

Folgendes Problem:

Ich habe meine Spielerfigur an der Position (x,y) und klicke irgendwo auf die map an die Stelle (x2,y2).
Ich berechne nun
dx = x2-x1
dy = y2-y1
Da ich die Spielerfigur in jedem Durchlaufen des Hauptloops nur um ein wenig verschieben möchte, so dass sie nicht über das Spielfeld rast, berechne ich weiterhin:
r = Abstand von der Spielerfigur zum Mausklick
dx = dx/r
dy = dy/r

Dies führt natürlich zu Werten zwischen 0 und 1, die move funktion für die Spielerfigur frisst jedoch nur ganze Zahlen, da es keine halben Pixel gibt etc.

Heisst: Die Figur läuft entweder rechts, links, nach oben, nach unten, diagonal.

Wenn ich dx und dy an jeder neuen Position erneut berechne, sieht das ganze etwas besser aus, jedoch wird das ganze so nur schlecht approximiert und die Figur stottert rum.
Teile ich dx und dy nicht durch r, sondern durch eine kleine Zahl, ist die Richtung zwar genauer, jedoch bewegt sich die Figur in weniger Bilder über das Spielfeld.

Habt ihr irgendeine Idee wie ich so eine flüssige Bewegung hinbekomme? Oder geht das mit einfachem Verschieben der Figur gar nicht?

[xxx]

Du könntest deine Figur 1px je Richtung pro Zeitintervall (z.B. 1/24 Sekunde) laufen lassen. Das sollte eine flüssige Bewegung erzeugen.

Von der Idee her:

Code: Alles auswählen

t0 = time.time()
while 1:
    t1 = time.time()
    if ((t1 - t0) >= 1/24.0):
        if dx != 0: 
            geheX(...)
        if dy != 0: 
            geheY(...)
        t0 = time.time()

[Phelot]

Du könntest deine Figur 1px je Richtung pro Zeitintervall (z.B. 1/24 Sekunde) laufen lassen. Das sollte eine flüssige Bewegung erzeugen.

Von der Idee her:

Code: Alles auswählen

t0 = time.time()
while 1:
    t1 = time.time()
    if ((t1 - t0) >= 1/24):
        if dx != 0: 
            geheX(...)
        if dy != 0: 
            geheY(...)
        t0 = time.time()

hm, werde das ganze mal ausprobieren danke!

/edit,

habe das ganze mal nun (hoffentlich richtig) angepasst. wenn die spielerfigur einer relativ schrägen (bis fast diagonal) linie folgen soll, ist immernoch ein ruckeln zu vernehmen. bei schwach schrägen (fast geraden) linien geht er immernoch eine weile einfach geradeaus und lenkt dann auf eine schrägere richtung ein.

Code: Alles auswählen

t1 = time.time()

while True:

    if (t1-t0) >= 1/50:
        # momentane mausposition
        mouse_x, mouse_y = pygame.mouse.get_pos()
        
        # dx vom spieler zur maus
        dx = mouse_x - player.rect.centerx
        # dy vom spieler zur maus
        dy = mouse_y - player.rect.centery
        
        # distanz zur mouseposition
        distance_to_mouse = math.sqrt(dx**2 + dy**2)
        
        if distance_to_mouse != 0: # division durch 0
            player.dx = round(dx/distance_to_mouse, 0)
            player.dy = round(dy/distance_to_mouse, 0)
        
        player.rect = player.rect.move(player.dx, player.dy) # neue position
            
        t0 = t1


    
    screen.blit(level.image, (0,0)) # blit hintergrund
   
    screen.blit(player.image, player.rect) # blit spieler
    
    screen.blit(ui.bottom.image, (0,510)) # blit ui
    pygame.display.update() 
    pygame.time.wait(20) # warte 20ms
    pygame.display.flip()

[xxx]

Ich habe mal eine kleinen Prototyp nachgebastelt damit ich das Ruckeln sehe. Eine einfache Methode das Ruckeln wegzubekommen ist statt (dx/sqrt(dx^2 + dy^2)) einfach 1 zu nehmen. Damit die Richtung richtig ist, kannst du math.copysign(1, dx) nehmen.

Code: Alles auswählen

import pygame
import time
import math

pygame.init()

screen = pygame.display.set_mode([600,480])

clock = pygame.time.Clock()

background = pygame.image.load("b.jpg").convert()

player = pygame.image.load("x.jpg").convert()

x = 5
y = 20

pX = x
pY = y

t0 = time.time()
while 1:
    for event in pygame.event.get():
        if event.type == pygame.MOUSEBUTTONDOWN:
            pX, pY = pygame.mouse.get_pos()
    
    t1 = time.time()
    if (t1 - t0) >= 1/120.0:
        dx = pX - x    
        dy = pY - y
        
        #print dx, dy, t1, t0, (t1 - t0)

        if dx != 0:
            x += math.copysign(1, dx)
        if dy != 0:
            y += math.copysign(1, dy)

        t0 = time.time()
            
   
    screen.fill((0,0,0))

    screen.blit(background, [0,0])
    screen.blit(player, [x, y])
    
    pygame.display.update()
    pygame.display.flip()

[EviLsEyE]

Du kannst die Koordinaten auch einfach als Float-Werte behandeln und beim Zeichnen der Position eben entsprechend runden..
Sieht dann ausreichend flüssig aus

Anm: das ist ein genereller Tipp, nicht aufs Toolkit oder Python bezogen!

[Phelot]

Du kannst die Koordinaten auch einfach als Float-Werte behandeln und beim Zeichnen der Position eben entsprechend runden..
Sieht dann ausreichend flüssig aus

Anm: das ist ein genereller Tipp, nicht aufs Toolkit oder Python bezogen!

hmm, m.M.n. habe ich dies gemacht. So wie ich das verstanden habe, muss ich um eine flüssige Bewegung zu erzeugen, das Bild z.B. alle 1/25s auf eine position x+dx pixel seitlich und y+dy pixel vertikal neu zeichnen, sowie das bild auf der alten position löschen bzw. mit dem hintergrund übermalen. Dies funktioniert auch soweit, dass horizontale, vertikale und diagonale bewegungen flüssig sind.
Mein Problem liegt nun bei schrägen, nicht ganz diagonalen Bewegungen.

Hier ein Bild:
X bezeichnet die Position des Mausklicks, der rote bzw. hellblaue Strich zeichnet den Weg ein, die die Figur zurücklegt um dorthin zu gelangen. Wbei ich es so machen wollte, dass sie der gelben Linie entlang geht.



Bei schrägen, nicht diagonalen Linien (z.B. bei der roten) müsste sie ja in einem Frame ca. 5px nach rechts und 1px nach unten gehen. Dies führt jedoch zu einer 'ruckligeren' und schnelleren Bewegung. Versteht Ihr was ich meine?

Ich habe hier noch zwei Videos gemacht, das Erste ist von meinem, das Zweite von xxx's Code. Sah das bei dir ähnlich aus xxx?

main1.avi - YouTube

main2 - YouTube

Die Bewegung ist in beiden Varianten etwa gleich wobei sie in xxx Variante etwas flüssiger ist. Dieses Ruckeln bei horizontalen/diagonalen/vertikalen Bewegungen entstand wahrscheinlich durch die Aufnahme. Mit meinem Krüppelcode von vorhin versuchte ich diese schrägen Linien ablaufen zu können, wobei die Figur bei diesen eben anfängt rumzustottern. Ich hoffe das ist in dieser Auflösung erkennbar

Ich habe das Gefühl, dass ich irgendetwas Grundlegendes nicht wirklich gerafft habe.

[xxx]

Geht es darum, dass die Figur einfach einen zu großen Weg pro Frame zurücklegt? Oder um das "hin und her" z.B. bei 0:52-53 im 1. Video?

[Phelot]

Geht es darum, dass die Figur einfach einen zu großen Weg pro Frame zurücklegt?

Ja im Grunde schon. Mit diesem 'dx,dy'-Ansatz geht sie doch bei einer horizontalen Bewegung pro frame z.B. ein Pixel nach rechts. Bei einer schrägen Linie müsste sie aber, um halbwegs auf der Linie zu bleiben, z.B. 5px nach rechts und 1px nach unten gehen. Was ja zu einer grösseren Distanz führt.
Mein grundlegendes Logikproblem: Ich habe eine Figur an einer Position und klicke irgendwohin. Die Figur in einem Frame dorthin zu bewegen wäre ja kein Problem. Um jedoch viele Zwischenschritte aus dieser einen Bewegung zu erzeugen, muss ich die Spielerfigur ja mehrmals auf der Linie, die die Position der Spielerfigur mit der Position des Mausklicks verbindet, verschieben. Da mathematisch gesehen jedoch nicht alle Punkte dieser Linie integer Koordinaten haben und es keine ungeraden Pixel gibt, habe ich ein Problem die Linie gerade abzulaufen.
Irgendwie kann ich mir nicht vorstellen, wie man dies ohne komplizierte Approximierungsalgorithmen lösen kann. Oder aber ich stehe mir einfach massiv auf dem Schlauch.

@Evilseye, Angenommen ich habe dich richtig verstanden: Bei der Verschiebung um ein Pixel versuchte ich ebenfalls die dx,dy Werte zu runden (was eigentlich das gleiche wie math.copysign(1, dx) bzw. math.copysign(1, dy)) sein müsste. Dies führt jedoch irgendwie dazu, dass die Spielerfigur solange um dx=1, dy=1 verschoben wird, bis sie einer Horizontalen/Vertikalen folgen kann (dx=0,dy=1 bzw. dx=1, dy=0).

/edit,

[...] Oder um das "hin und her" z.B. bei 0:52-53 im 1. Video?

Dieses hin und her ist wahrscheinlich irgend ein Fehler in meinem Code. Das hatte ich in meinem letzten Entwurf iirc nicht.

[xxx]

Ah, ich glaube nun weiß ich was das Problem ist.

Du hast deine ideale Linie auf deinem Pixelraster:


Und die möchtest du irgendwie approximieren:


Was du wahrscheinlich suchst: Bresenham-Algorithmus – Wikipedia (sehr einfach)

Da bin ich echt extrem fett auf dem Schlauch gestanden, dachte anfangs, dass du ein Timingproblem hast

[Phelot]

Ah, ich glaube nun weiß ich was das Problem ist.

Du hast deine ideale Linie auf deinem Pixelraster:


Und die möchtest du irgendwie approximieren:


Was du wahrscheinlich suchst: Bresenham-Algorithmus – Wikipedia (sehr einfach)

Da bin ich echt extrem fett auf dem Schlauch gestanden, dachte anfangs, dass du ein Timingproblem hast

OMG! Danke! Also gibt es das Problem tatsächlich. Habe mir nun mehrere Tage darüber den Kopf zerbrochen und ewigs im Internet gesucht
Thx!

/edit, habe nun schnell etwas zusammengeworfen. Bei jedem Mausklick werden mit dem Bresenham sämtliche x,y-Tupel berechnet, die diese Linie annähernd beschreiben und in einer list gespeichert. Die Grafik wird dann einfach entlang diesen Werten verschoben, bis sie ankommt oder ein neues array erzeugt wird. Zwar noch massiv buggy, aber es scheint zu gehen \o/

[EviLsEyE]

@Evilseye, Angenommen ich habe dich richtig verstanden: Bei der Verschiebung um ein Pixel versuchte ich ebenfalls die dx,dy Werte zu runden (was eigentlich das gleiche wie math.copysign(1, dx) bzw. math.copysign(1, dy)) sein müsste. Dies führt jedoch irgendwie dazu, dass die Spielerfigur solange um dx=1, dy=1 verschoben wird, bis sie einer Horizontalen/Vertikalen folgen kann (dx=0,dy=1 bzw. dx=1, dy=0).

Nee, nee.. so meinte ich das nicht..
Hier mal ein ganz stark vereinfachtes Beispiel, das ich aus 'nem alten C-Programm von mir hab (alter Schwede, das hab ich vor 7 Jahren gebastelt, wie die Zeit vergeht ).. xStart/yStart und xEnd/yEnd seien die Start- und Endpunkte und die folgende Routine berechnet den Weg dazwischen..

Code: Alles auswählen

[color=yellow]int dx = xEnd-xStart;
int dy = yEnd-yStart;[/color]
int steps;
int k;
	
float xOffset;
float yOffset;
float x = (float) xStart,
float y = (float) yStart;

if (dx > dy)
	steps = dx;
else
	steps = dy;
	
[color=green]xOffset = dx/(float)steps; 
yOffset = dy/(float)steps;[/color]

drawPoint(round(x), round(y));
for (k = 0; k < steps; k++)
{
	x += xOffset;
	y += yOffset;
	drawPoint(round(x), round(y));
}

Gelb: Berechnung der horizontalen und vertikalen Distanz zwischen Start- und Endpunkt (kommt 'ne Ganzzahl bei raus)
Grün: Berechnung des Offsets, das pro Animationsschritt aufaddiert wird (genaugenommen ist es kein Offset, sondern ein Delta-Wert).. wichtig hier: das is 'n Float! Dadurch kriegt man auch [x/y] Koordinaten wie [15.6/13.4], die dann gerundet entsprechend einer angenäherten Geraden entsprechen

[Phelot]

Nee, nee.. so meinte ich das nicht..
Hier mal ein ganz stark vereinfachtes Beispiel, das ich aus 'nem alten C-Programm von mir hab (alter Schwede, das hab ich vor 7 Jahren gebastelt, wie die Zeit vergeht ).. xStart/yStart und xEnd/yEnd seien die Start- und Endpunkte und die folgende Routine berechnet den Weg dazwischen..

Code: Alles auswählen

[color=yellow]int dx = xEnd-xStart;
int dy = yEnd-yStart;[/color]
int steps;
int k;
	
float xOffset;
float yOffset;
float x = (float) xStart,
float y = (float) yStart;

if (dx > dy)
	steps = dx;
else
	steps = dy;
	
[color=green]xOffset = dx/(float)steps; 
yOffset = dy/(float)steps;[/color]

drawPoint(round(x), round(y));
for (k = 0; k < steps; k++)
{
	x += xOffset;
	y += yOffset;
	drawPoint(round(x), round(y));
}

Gelb: Berechnung der horizontalen und vertikalen Distanz zwischen Start- und Endpunkt (kommt 'ne Ganzzahl bei raus)
Grün: Berechnung des Offsets, das pro Animationsschritt aufaddiert wird (genaugenommen ist es kein Offset, sondern ein Delta-Wert).. wichtig hier: das is 'n Float! Dadurch kriegt man auch [x/y] Koordinaten wie [15.6/13.4], die dann gerundet entsprechend einer angenäherten Geraden entsprechen

Ah ok, sry hab' dich in diesem Fall falsch verstanden. Scheint ebenfalls gut zu funktionieren. Ich war kurz davor mich an einem rekursiven divide and conquer Algorithmus zu versuchen, der solche Linien approximiert und der sicherlich eine unnötig höhere Laufzeit gehabt hätte (wenn ich es überhaupt geschafft hätte)
Kennt ihr irgendwelche Tutorials/Bücher, die sich mit den Programmierkonzepten der Game Programminerung und/oder Computer Grafik beschäftigen?
Danke euch beiden!