From ea2dbf13c21185da5693ebf4d37369a6fc2f73ff Mon Sep 17 00:00:00 2001 From: Martin Kagamino Lehoux Date: Sun, 3 Sep 2023 22:48:15 +0200 Subject: feat: Move with path finding --- go.mod | 4 +- go.sum | 4 ++ main.go | 90 +++++++++++++++++++++++++++++++++++------- move.go | 132 +++++++++++++++++++++++++++++++++++++++++++++++++++++++------- person.go | 4 +- 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() { -- cgit v1.3