feat: Move with path finding

5 files changed, 201 insertions, 33 deletions

diff --git a/go.mod b/go.mod
index 3fbe386..b3eaf92 100644
--- a/go.mod
+++ b/go.mod
@@ -8,9 +8,9 @@ require (
 	github.com/ebitengine/purego v0.4.0 // indirect
 	github.com/go-gl/glfw/v3.3/glfw v0.0.0-20221017161538-93cebf72946b // indirect
 	github.com/jezek/xgb v1.1.0 // indirect
-	golang.org/x/exp v0.0.0-20190731235908-ec7cb31e5a56 // indirect
+	golang.org/x/exp v0.0.0-20230817173708-d852ddb80c63 // indirect
 	golang.org/x/image v0.10.0 // indirect
 	golang.org/x/mobile v0.0.0-20230301163155-e0f57694e12c // indirect
 	golang.org/x/sync v0.1.0 // indirect
-	golang.org/x/sys v0.7.0 // indirect
+	golang.org/x/sys v0.11.0 // indirect
 )
diff --git a/go.sum b/go.sum
index afb30c6..3b6c32e 100644
--- a/go.sum
+++ b/go.sum
@@ -13,6 +13,8 @@ golang.org/x/crypto v0.0.0-20190510104115-cbcb75029529/go.mod h1:yigFU9vqHzYiE8U
 golang.org/x/crypto v0.0.0-20210921155107-089bfa567519/go.mod h1:GvvjBRRGRdwPK5ydBHafDWAxML/pGHZbMvKqRZ5+Abc=
 golang.org/x/exp v0.0.0-20190731235908-ec7cb31e5a56 h1:estk1glOnSVeJ9tdEZZc5mAMDZk5lNJNyJ6DvrBkTEU=
 golang.org/x/exp v0.0.0-20190731235908-ec7cb31e5a56/go.mod h1:JhuoJpWY28nO4Vef9tZUw9qufEGTyX1+7lmHxV5q5G4=
+golang.org/x/exp v0.0.0-20230817173708-d852ddb80c63 h1:m64FZMko/V45gv0bNmrNYoDEq8U5YUhetc9cBWKS1TQ=
+golang.org/x/exp v0.0.0-20230817173708-d852ddb80c63/go.mod h1:0v4NqG35kSWCMzLaMeX+IQrlSnVE/bqGSyC2cz/9Le8=
 golang.org/x/image v0.0.0-20190227222117-0694c2d4d067/go.mod h1:kZ7UVZpmo3dzQBMxlp+ypCbDeSB+sBbTgSJuh5dn5js=
 golang.org/x/image v0.10.0 h1:gXjUUtwtx5yOE0VKWq1CH4IJAClq4UGgUA3i+rpON9M=
 golang.org/x/image v0.10.0/go.mod h1:jtrku+n79PfroUbvDdeUWMAI+heR786BofxrbiSF+J0=
@@ -41,6 +43,8 @@ golang.org/x/sys v0.0.0-20220722155257-8c9f86f7a55f/go.mod h1:oPkhp1MJrh7nUepCBc
 golang.org/x/sys v0.5.0/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/sys v0.7.0 h1:3jlCCIQZPdOYu1h8BkNvLz8Kgwtae2cagcG/VamtZRU=
 golang.org/x/sys v0.7.0/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/sys v0.11.0 h1:eG7RXZHdqOJ1i+0lgLgCpSXAp6M3LYlAo6osgSi0xOM=
+golang.org/x/sys v0.11.0/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/term v0.0.0-20201126162022-7de9c90e9dd1/go.mod h1:bj7SfCRtBDWHUb9snDiAeCFNEtKQo2Wmx5Cou7ajbmo=
 golang.org/x/term v0.0.0-20210927222741-03fcf44c2211/go.mod h1:jbD1KX2456YbFQfuXm/mYQcufACuNUgVhRMnK/tPxf8=
 golang.org/x/term v0.5.0/go.mod h1:jMB1sMXY+tzblOD4FWmEbocvup2/aLOaQEp7JmGp78k=
diff --git a/main.go b/main.go
index dd36ea1..68df4f2 100644
--- a/main.go
+++ b/main.go
@@ -8,6 +8,13 @@ import (
 	"github.com/hajimehoshi/ebiten/v2/vector"
 )
 
+type Action string
+
+const (
+	Selecting   Action = "selecting"
+	PlacingWall Action = "placing-wall"
+)
+
 type Tile struct {
 	*ebiten.Image
 	Size     Point
@@ -20,8 +27,13 @@ func NewTile(size Point, position Point, color color.Color) Tile {
 	return Tile{Size: size, Position: position, Image: image}
 }
 
+func (t Tile) CollisionBounds() Rectangle {
+	return Rectangle{t.Position, t.Position.Add(t.Size)}
+}
+
 var soilColor = color.RGBA{0x60, 0x40, 0x20, 0xff}
 var soil = NewTile(Point{2800, 2000}, Point{200, 200}, soilColor)
+var wallButton = NewTile(Point{100, 100}, Point{50, 50}, color.RGBA{0x00, 0x00, 0x00, 0xff})
 
 type Selection struct {
 	IsActive bool
@@ -29,20 +41,22 @@ type Selection struct {
 }
 
 type Game struct {
-	Persons   []*Person
-	Selection Selection
+	Persons       []*Person
+	CurrentAction Action
+	Selection     Selection
+	Walls         []Tile
 }
 
-func (g *Game) Update() error {
-	x, y := ebiten.CursorPosition()
+func (g *Game) updateSelecting(cursor Point) {
 	if inpututil.IsMouseButtonJustPressed(ebiten.MouseButtonLeft) {
-		g.Selection.Start = Point{x, y}
+		g.Selection.Start = cursor
 		g.Selection.IsActive = true
 	}
 	if inpututil.IsMouseButtonJustReleased(ebiten.MouseButtonRight) {
-		destination := Point{
-			(x-soil.Position.X)/100*100 + 50,
-			(y-soil.Position.Y)/100*100 + 50,
+		destination := cursor.Sub(soil.Position).Div(100).Mul(100).Add(Point{50, 50})
+		blocked := map[Point]bool{}
+		for _, w := range g.Walls {
+			blocked[w.Position] = true
 		}
 		for _, p := range g.Persons {
 			if p.IsSelected {
@@ -51,17 +65,16 @@ func (g *Game) Update() error {
 					destination.Add(p.size.Div(2)),
 				}
 				if futureBounds.In(soil.Bounds()) {
-					p.MoveTo(destination)
+					p.MoveTo(destination, blocked)
 				}
 			}
 		}
 	}
 	if inpututil.IsMouseButtonJustReleased(ebiten.MouseButtonLeft) {
-		tileClick := Point{x - soil.Position.X, y - soil.Position.Y}
-		if g.Selection.IsActive && Distance(g.Selection.Start, Point{x, y}) > 10 {
+		if g.Selection.IsActive && Distance(g.Selection.Start, cursor) > 10 {
 			for _, p := range g.Persons {
 				p.IsSelected = false
-				selectionBounds := Rectangle{g.Selection.Start.Sub(soil.Position), tileClick}.Canon()
+				selectionBounds := Rectangle{g.Selection.Start.Sub(soil.Position), cursor.Sub(soil.Position)}.Canon()
 				if selectionBounds.Overlaps(p.CollisionBounds()) {
 					p.IsSelected = true
 				}
@@ -70,14 +83,46 @@ func (g *Game) Update() error {
 			canBeSelected := true
 			for _, p := range g.Persons {
 				p.IsSelected = false
-				if tileClick.In(p.CollisionBounds()) {
+				if cursor.Sub(soil.Position).In(p.CollisionBounds()) {
 					p.IsSelected = canBeSelected
 					canBeSelected = false
 				}
 			}
 		}
 		g.Selection.IsActive = false
+	}
+}
 
+func (g *Game) updatePlacingWall(cursor Point) {
+	if inpututil.IsMouseButtonJustReleased(ebiten.MouseButtonLeft) {
+		if cursor.In(soil.Bounds()) {
+			position := cursor.Sub(soil.Position).Div(100).Mul(100).Add(Point{50, 50})
+			g.Walls = append(g.Walls, NewTile(Point{100, 100}, position, color.RGBA{0x00, 0x00, 0x00, 0xff}))
+		}
+	}
+}
+
+func (g *Game) Update() error {
+	x, y := ebiten.CursorPosition()
+	cursor := Point{x, y}
+	if inpututil.IsMouseButtonJustReleased(ebiten.MouseButtonLeft) && cursor.In(wallButton.CollisionBounds()) {
+		if g.CurrentAction == PlacingWall {
+			g.CurrentAction = Selecting
+		} else {
+			g.CurrentAction = PlacingWall
+		}
+	}
+	if inpututil.IsKeyJustReleased(ebiten.KeyEscape) {
+		g.CurrentAction = Selecting
+	}
+	switch g.CurrentAction {
+	case Selecting:
+		g.updateSelecting(cursor)
+	case PlacingWall:
+		if g.Selection.IsActive {
+			g.Selection.IsActive = false
+		}
+		g.updatePlacingWall(cursor)
 	}
 	for _, p := range g.Persons {
 		p.Update()
@@ -88,18 +133,31 @@ func (g *Game) Update() error {
 func (g *Game) Draw(screen *ebiten.Image) {
 	screen.Fill(color.RGBA{0x80, 0xa0, 0xc0, 0xff})
 	soil.Fill(soilColor)
+	for _, w := range g.Walls {
+		bounds := w.Image.Bounds()
+		op := &ebiten.DrawImageOptions{}
+		op.GeoM.Translate(float64(w.Position.X-bounds.Dx()/2), float64(w.Position.Y-bounds.Dy()/2))
+		soil.DrawImage(w.Image, op)
+	}
 	for _, p := range g.Persons {
 		bounds := p.Image().Bounds()
 		op := &ebiten.DrawImageOptions{}
 		op.GeoM.Translate(float64(p.Position.X-bounds.Dx()/2), float64(p.Position.Y-bounds.Dy()/2))
 		soil.DrawImage(p.Image(), op)
 		if p.IsSelected && p.move.IsActive {
-			vector.StrokeLine(soil.Image, float32(p.Position.X), float32(p.Position.Y), float32(p.move.Destination.X), float32(p.move.Destination.Y), 10.0, color.RGBA{256 * 3 / 16, 256 * 3 / 16, 256 * 3 / 16, 256 / 4}, true)
+			last := p.Position
+			for _, point := range p.move.Path {
+				vector.StrokeLine(soil.Image, float32(last.X), float32(last.Y), float32(point.X), float32(point.Y), 10.0, color.RGBA{256 * 3 / 16, 256 * 3 / 16, 256 * 3 / 16, 256 / 4}, true)
+				last = point
+			}
 		}
 	}
 	op := &ebiten.DrawImageOptions{}
 	op.GeoM.Translate(float64(soil.Position.X), float64(soil.Position.Y))
 	screen.DrawImage(soil.Image, op)
+	op = &ebiten.DrawImageOptions{}
+	op.GeoM.Translate(float64(wallButton.Position.X), float64(wallButton.Position.Y))
+	screen.DrawImage(wallButton.Image, op)
 	if g.Selection.IsActive {
 		x, y := ebiten.CursorPosition()
 		screenClick := Point{x, y}
@@ -119,6 +177,10 @@ func main() {
 	nonPlayerPerson := NewPerson(Point{400, 400})
 	game.Persons = append(game.Persons, &mainPerson)
 	game.Persons = append(game.Persons, &nonPlayerPerson)
+	game.CurrentAction = Selecting
+	for i := 0; i < 10; i++ {
+		game.Walls = append(game.Walls, NewTile(Point{100, 100}, Point{350 + i*100, 350}, color.RGBA{0x00, 0x00, 0x00, 0xff}))
+	}
 	if err := ebiten.RunGame(game); err != nil {
 		panic(err)
 	}
diff --git a/move.go b/move.go
index 97d4809..d6c0707 100644
--- a/move.go
+++ b/move.go
@@ -1,45 +1,147 @@
 package main
 
 import (
+	"fmt"
 	"math"
+
+	"golang.org/x/exp/slices"
 )
 
 type Move struct {
 	IsActive    bool
 	Origin      Point
 	Destination Point
-	Nodes       []Point
+	Path        []Point
+}
+
+type Node struct {
+	CostFromOrigin    int
+	CostToDestination int
+	Parent            Point
+}
+
+func (n Node) Cost() int {
+	return n.CostFromOrigin + n.CostToDestination
+}
+
+type PathSearch struct {
+	origin      Point
+	destination Point
+	openList    map[Point]Node
+	closedList  map[Point]Node
+	blocked     map[Point]bool
+}
+
+func SearchPath(origin Point, destination Point, blocked map[Point]bool) ([]Point, bool) {
+	search := PathSearch{
+		origin:      origin,
+		destination: destination,
+		openList:    map[Point]Node{},
+		closedList:  map[Point]Node{},
+		blocked:     blocked,
+	}
+	return search.search()
 }
 
-func NewMove(origin Point, destination Point) Move {
-	nodes := []Point{}
+func (s *PathSearch) addNeighbours(point Point, node Node) {
+	if point.X >= 100 {
+		s.consider(Point{point.X - 100, point.Y}, point)
+	}
+	if point.X <= soil.Size.X-100 {
+		s.consider(Point{point.X + 100, point.Y}, point)
+	}
+	if point.Y >= 100 {
+		s.consider(Point{point.X, point.Y - 100}, point)
+	}
+	if point.Y <= soil.Size.Y-100 {
+		s.consider(Point{point.X, point.Y + 100}, point)
+	}
+}
+
+func (s *PathSearch) consider(neighbor Point, point Point) {
+	if s.blocked[neighbor] {
+		return
+	}
+	if _, ok := s.closedList[neighbor]; !ok {
+		node := Node{
+			CostFromOrigin:    s.closedList[point].CostFromOrigin + int(Distance(point, neighbor)),
+			CostToDestination: int(Distance(neighbor, s.destination)),
+			Parent:            point,
+		}
+		existing, ok := s.openList[neighbor]
+		if !ok || existing.Cost() > node.Cost() {
+			s.openList[neighbor] = node
+		}
+	}
+}
+
+// openList must not be empty
+func (s *PathSearch) bestOpenNode() (Point, Node) {
+	bestPoint := Point{}
+	bestNode := Node{}
+	bestCost := math.MaxInt32
+	for point, node := range s.openList {
+		if cost := node.Cost(); cost < bestCost {
+			bestPoint = point
+			bestNode = node
+			bestCost = cost
+		}
+	}
+	return bestPoint, bestNode
+}
+
+func (s *PathSearch) buildPath() []Point {
+	point := s.destination
+	path := []Point{s.destination}
+	node := s.closedList[s.destination]
+	for point != s.origin {
+		point = node.Parent
+		path = append(path, point)
+		node = s.closedList[point]
+	}
+	slices.Reverse(path)
+	return path
+}
+
+func (s *PathSearch) search() ([]Point, bool) {
+	s.openList[s.origin] = Node{CostFromOrigin: 0, CostToDestination: int(Distance(s.origin, s.destination)), Parent: s.origin}
+	point := s.origin
+	var node Node
+	for point != s.destination && len(s.openList) > 0 {
+		point, node = s.bestOpenNode()
+		s.closedList[point] = node
+		delete(s.openList, point)
+		s.addNeighbours(point, node)
+	}
+	if point == s.destination {
+		return s.buildPath(), true
+	}
+	return []Point{}, false
+}
+
+func NewMove(origin Point, destination Point, blocked map[Point]bool) Move {
 	current := Point{
 		origin.X/100*100 + 50,
 		origin.Y/100*100 + 50,
 	}
-	for current != destination {
-		next := current
-		if math.Abs(float64(destination.X-current.X)) > math.Abs(float64(destination.Y-current.Y)) {
-			next.X = current.X + int(math.Copysign(100, float64(destination.X-current.X)))
-		} else {
-			next.Y = current.Y + int(math.Copysign(100, float64(destination.Y-current.Y)))
-		}
-		nodes = append(nodes, next)
-		current = next
+	search, ok := SearchPath(current, destination, blocked)
+	if !ok {
+		fmt.Println("No path found")
+		return Move{IsActive: false}
 	}
-	return Move{IsActive: true, Origin: origin, Destination: destination, Nodes: nodes}
+	return Move{IsActive: true, Origin: origin, Destination: destination, Path: search}
 }
 
 func (m *Move) Update(position Point, speed int) Point {
 	if !m.IsActive {
 		return position
 	}
-	next := m.Nodes[0]
+	next := m.Path[0]
 	if Distance(position, next) < float64(speed) {
 		if next == m.Destination {
 			m.IsActive = false
 		} else {
-			m.Nodes = m.Nodes[1:]
+			m.Path = m.Path[1:]
 		}
 		return next
 	}
diff --git a/person.go b/person.go
index 66e30cd..4ddeddc 100644
--- a/person.go
+++ b/person.go
@@ -40,8 +40,8 @@ func (p Person) CollisionBounds() Rectangle {
 	}
 }
 
-func (p *Person) MoveTo(destination Point) {
-	p.move = NewMove(p.Position, destination)
+func (p *Person) MoveTo(destination Point, blocked map[Point]bool) {
+	p.move = NewMove(p.Position, destination, blocked)
 }
 
 func (p *Person) Update() {