snakesimulator.go 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520
  1. /*
  2. * MIT License
  3. *
  4. * Copyright (c) 2019 Alexey Edelev <semlanik@gmail.com>
  5. *
  6. * This file is part of NeuralNetwork project https://git.semlanik.org/semlanik/NeuralNetwork
  7. *
  8. * Permission is hereby granted, free of charge, to any person obtaining a copy of this
  9. * software and associated documentation files (the "Software"), to deal in the Software
  10. * without restriction, including without limitation the rights to use, copy, modify,
  11. * merge, publish, distribute, sublicense, and/or sell copies of the Software, and
  12. * to permit persons to whom the Software is furnished to do so, subject to the following
  13. * conditions:
  14. *
  15. * The above copyright notice and this permission notice shall be included in all copies
  16. * or substantial portions of the Software.
  17. *
  18. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
  19. * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  20. * PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
  21. * FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
  22. * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  23. * DEALINGS IN THE SOFTWARE.
  24. */
  25. package snakesimulator
  26. import (
  27. context "context"
  28. fmt "fmt"
  29. math "math"
  30. "math/rand"
  31. "net"
  32. "sort"
  33. "sync"
  34. "time"
  35. "gonum.org/v1/gonum/mat"
  36. genetic "git.semlanik.org/semlanik/NeuralNetwork/genetic"
  37. neuralnetwork "git.semlanik.org/semlanik/NeuralNetwork/neuralnetwork"
  38. remotecontrol "git.semlanik.org/semlanik/NeuralNetwork/remotecontrol"
  39. grpc "google.golang.org/grpc"
  40. )
  41. type SnakeSimulator struct {
  42. field *Field
  43. snake *Snake
  44. maxVerificationSteps int
  45. stats *Stats
  46. remoteControl *remotecontrol.RemoteControl
  47. //GUI interface part
  48. speed uint32
  49. fieldUpdateQueue chan bool
  50. snakeUpdateQueue chan bool
  51. statsUpdateQueue chan bool
  52. isPlayingUpdateQueue chan bool
  53. speedQueue chan uint32
  54. isPlaying bool
  55. repeatInLoop bool
  56. snakeReadMutex sync.Mutex
  57. fieldReadMutex sync.Mutex
  58. }
  59. // Initializes new snake population with maximum number of verification steps
  60. func NewSnakeSimulator(maxVerificationSteps int) (s *SnakeSimulator) {
  61. s = &SnakeSimulator{
  62. field: &Field{
  63. Food: &Point{},
  64. Width: 40,
  65. Height: 40,
  66. },
  67. snake: &Snake{
  68. Points: []*Point{
  69. &Point{X: 20, Y: 20},
  70. &Point{X: 21, Y: 20},
  71. &Point{X: 22, Y: 20},
  72. },
  73. },
  74. stats: &Stats{},
  75. maxVerificationSteps: maxVerificationSteps,
  76. fieldUpdateQueue: make(chan bool, 2),
  77. snakeUpdateQueue: make(chan bool, 2),
  78. statsUpdateQueue: make(chan bool, 2),
  79. isPlayingUpdateQueue: make(chan bool, 1),
  80. speedQueue: make(chan uint32, 1),
  81. speed: 10,
  82. remoteControl: remotecontrol.NewRemoteControl(),
  83. }
  84. return
  85. }
  86. // Population test method
  87. // Verifies population and returns unsorted finteses for each individual
  88. func (s *SnakeSimulator) Verify(population *genetic.Population) (fitnesses []*genetic.IndividalFitness) {
  89. s.remoteControl.Init(population.Networks[0])
  90. s.stats.Generation++
  91. s.statsUpdateQueue <- true
  92. s.field.GenerateNextFood()
  93. if s.speed > 0 {
  94. s.fieldUpdateQueue <- true
  95. }
  96. fitnesses = make([]*genetic.IndividalFitness, len(population.Networks))
  97. for index, inidividual := range population.Networks {
  98. s.stats.Individual = uint32(index)
  99. s.statsUpdateQueue <- true
  100. s.runSnake(inidividual, false)
  101. fitnesses[index] = &genetic.IndividalFitness{
  102. // Fitness: float64(s.stats.Move), //Uncomment this to decrese food impact to individual selection
  103. Fitness: float64(s.stats.Move) * float64(len(s.snake.Points)-2),
  104. Index: index,
  105. }
  106. }
  107. //This is duplication of crossbreedPopulation functionality to display best snake
  108. sort.Slice(fitnesses, func(i, j int) bool {
  109. return fitnesses[i].Fitness > fitnesses[j].Fitness //Descent order best will be on top, worst in the bottom
  110. })
  111. //Best snake showtime!
  112. s.fieldReadMutex.Lock()
  113. s.field.GenerateNextFood()
  114. s.fieldReadMutex.Unlock()
  115. s.fieldUpdateQueue <- true
  116. prevSpeed := s.speed
  117. s.speed = 5
  118. if s.isPlaying == true {
  119. // Play best of the best
  120. s.isPlaying = false
  121. s.isPlayingUpdateQueue <- s.isPlaying
  122. population.GetBestNetwork().SetStateWatcher(s.remoteControl)
  123. s.runSnake(population.GetBestNetwork(), false)
  124. population.GetBestNetwork().SetStateWatcher(nil)
  125. } else {
  126. // Pley best from generation
  127. population.Networks[fitnesses[0].Index].SetStateWatcher(s.remoteControl)
  128. s.runSnake(population.Networks[fitnesses[0].Index], false)
  129. population.Networks[fitnesses[0].Index].SetStateWatcher(nil)
  130. }
  131. s.speed = prevSpeed
  132. return
  133. }
  134. func (s *SnakeSimulator) PlayBestNetwork(network *neuralnetwork.NeuralNetwork) {
  135. for s.repeatInLoop {
  136. s.remoteControl.Init(network)
  137. s.stats.Generation++
  138. s.statsUpdateQueue <- true
  139. s.field.GenerateNextFood()
  140. if s.speed > 0 {
  141. s.fieldUpdateQueue <- true
  142. }
  143. //Best snake showtime!
  144. s.fieldReadMutex.Lock()
  145. s.field.GenerateNextFood()
  146. s.fieldReadMutex.Unlock()
  147. s.fieldUpdateQueue <- true
  148. s.isPlaying = false
  149. s.isPlayingUpdateQueue <- s.isPlaying
  150. prevSpeed := s.speed
  151. s.speed = 5
  152. network.SetStateWatcher(s.remoteControl)
  153. s.runSnake(network, false)
  154. network.SetStateWatcher(nil)
  155. s.speed = prevSpeed
  156. }
  157. }
  158. func (s *SnakeSimulator) runSnake(inidividual *neuralnetwork.NeuralNetwork, randomStart bool) {
  159. s.snakeReadMutex.Lock()
  160. if randomStart {
  161. rand.Seed(time.Now().UnixNano())
  162. s.snake = NewSnake(Direction(rand.Uint32()%4), *s.field)
  163. } else {
  164. s.snake = NewSnake(Direction_Left, *s.field)
  165. }
  166. s.snakeReadMutex.Unlock()
  167. s.stats.Move = 0
  168. for i := 0; i < s.maxVerificationSteps; i++ {
  169. //Read speed from client and sleep in case if user selected slow preview
  170. select {
  171. case newSpeed := <-s.speedQueue:
  172. fmt.Printf("Apply new speed: %v\n", newSpeed)
  173. if newSpeed <= 10 && newSpeed >= 0 {
  174. s.speed = newSpeed
  175. } else if newSpeed < 0 {
  176. s.speed = 0
  177. }
  178. default:
  179. }
  180. if s.speed > 0 {
  181. time.Sleep(100 / time.Duration(s.speed) * time.Millisecond)
  182. s.statsUpdateQueue <- true
  183. s.snakeUpdateQueue <- true
  184. }
  185. predictIndex, _ := inidividual.Predict(mat.NewDense(inidividual.Sizes[0], 1, s.getHeadState()))
  186. direction := Direction(predictIndex + 1)
  187. newHead := s.snake.NewHead(direction)
  188. if s.snake.selfCollision(newHead, direction) {
  189. fmt.Printf("Game over self collision\n")
  190. break
  191. } else if wallCollision(newHead, *s.field) {
  192. break
  193. } else if foodCollision(newHead, s.field.Food) {
  194. i = 0
  195. s.snakeReadMutex.Lock()
  196. s.snake.Feed(newHead)
  197. s.snakeReadMutex.Unlock()
  198. s.fieldReadMutex.Lock()
  199. s.field.GenerateNextFood()
  200. s.fieldReadMutex.Unlock()
  201. if s.speed > 0 {
  202. s.fieldUpdateQueue <- true
  203. }
  204. } else {
  205. s.snakeReadMutex.Lock()
  206. s.snake.Move(newHead)
  207. s.snakeReadMutex.Unlock()
  208. }
  209. s.stats.Move++
  210. }
  211. }
  212. // Produces input activations for neural network
  213. func (s *SnakeSimulator) getHeadState() []float64 {
  214. // Snake state
  215. headX := float64(s.snake.Points[0].X)
  216. headY := float64(s.snake.Points[0].Y)
  217. tailX := float64(s.snake.Points[len(s.snake.Points)-1].X)
  218. tailY := float64(s.snake.Points[len(s.snake.Points)-1].Y)
  219. // Field state
  220. foodX := float64(s.field.Food.X)
  221. foodY := float64(s.field.Food.Y)
  222. width := float64(s.field.Width)
  223. height := float64(s.field.Height)
  224. diag := float64(width) * math.Sqrt2 //We assume that field is always square
  225. // Output activations
  226. // Distance to walls in 4 directions
  227. lWall := headX
  228. rWall := (width - headX)
  229. tWall := headY
  230. bWall := (height - headY)
  231. // Distance to walls in 4 diagonal directions, by default is completely inactive
  232. tlWall := float64(0)
  233. trWall := float64(0)
  234. blWall := float64(0)
  235. brWall := float64(0)
  236. // Distance to food in 4 directions
  237. // By default is size of field that means that there is no activation at all
  238. lFood := float64(width)
  239. rFood := float64(width)
  240. tFood := float64(height)
  241. bFood := float64(height)
  242. // Distance to food in 4 diagonal directions
  243. // By default is size of field diagonal that means that there is no activation
  244. // at all
  245. tlFood := float64(diag)
  246. trFood := float64(diag)
  247. blFood := float64(diag)
  248. brFood := float64(diag)
  249. // Distance to tail in 4 directions
  250. tTail := float64(0)
  251. bTail := float64(0)
  252. lTail := float64(0)
  253. rTail := float64(0)
  254. // Distance to tail in 4 diagonal directions
  255. tlTail := float64(0)
  256. trTail := float64(0)
  257. blTail := float64(0)
  258. brTail := float64(0)
  259. // Diagonal distance to each wall
  260. if lWall > tWall {
  261. tlWall = float64(tWall) * math.Sqrt2
  262. } else {
  263. tlWall = float64(lWall) * math.Sqrt2
  264. }
  265. if rWall > tWall {
  266. trWall = float64(tWall) * math.Sqrt2
  267. } else {
  268. trWall = float64(rWall) * math.Sqrt2
  269. }
  270. if lWall > bWall {
  271. blWall = float64(bWall) * math.Sqrt2
  272. } else {
  273. blWall = float64(lWall) * math.Sqrt2
  274. }
  275. if rWall > bWall {
  276. blWall = float64(bWall) * math.Sqrt2
  277. } else {
  278. brWall = float64(rWall) * math.Sqrt2
  279. }
  280. // Check if food is on same vertical line with head and
  281. // choose vertical direction for activation
  282. if headX == foodX {
  283. if headY-foodY > 0 {
  284. tFood = 0
  285. } else {
  286. bFood = 0
  287. }
  288. }
  289. // Check if food is on same horizontal line with head and
  290. // choose horizontal direction for activation
  291. if headY == foodY {
  292. if headX-foodX > 0 {
  293. lFood = 0
  294. } else {
  295. rFood = 0
  296. }
  297. }
  298. //Check if food is on diagonal any of 4 ways
  299. if math.Abs(foodY-headY) == math.Abs(foodX-headX) {
  300. //Choose diagonal direction to food
  301. if foodX > headX {
  302. if foodY > headY {
  303. trFood = 0
  304. } else {
  305. brFood = 0
  306. }
  307. } else {
  308. if foodY > headY {
  309. tlFood = 0
  310. } else {
  311. blFood = 0
  312. }
  313. }
  314. }
  315. // Check if tail is on same vertical line with head and
  316. // choose vertical direction for activation
  317. if headX == tailX {
  318. if headY-tailY > 0 {
  319. tTail = headY - tailY
  320. } else {
  321. bTail = headY - tailY
  322. }
  323. }
  324. // Check if tail is on same horizontal line with head and
  325. // choose horizontal direction for activation
  326. if headY == tailY {
  327. if headX-tailX > 0 {
  328. rTail = headX - tailX
  329. } else {
  330. lTail = headX - tailX
  331. }
  332. }
  333. //Check if tail is on diagonal any of 4 ways
  334. if math.Abs(headY-tailY) == math.Abs(headX-tailX) {
  335. //Choose diagonal direction to tail
  336. if tailY > headY {
  337. if tailX > headX {
  338. trTail = diag
  339. } else {
  340. tlTail = diag
  341. }
  342. } else {
  343. if tailX > headX {
  344. brTail = diag
  345. } else {
  346. blTail = diag
  347. }
  348. }
  349. }
  350. return []float64{
  351. lWall / width,
  352. rWall / width,
  353. tWall / height,
  354. bWall / height,
  355. tlWall / diag,
  356. trWall / diag,
  357. blWall / diag,
  358. brWall / diag,
  359. (1.0 - lFood/width),
  360. (1.0 - rFood/width),
  361. (1.0 - tFood/height),
  362. (1.0 - bFood/height),
  363. (1.0 - tlFood/diag),
  364. (1.0 - trFood/diag),
  365. (1.0 - blFood/diag),
  366. (1.0 - brFood/diag),
  367. tTail / height,
  368. bTail / height,
  369. lTail / width,
  370. rTail / width,
  371. tlTail / diag,
  372. trTail / diag,
  373. blTail / diag,
  374. brTail / diag,
  375. }
  376. }
  377. // Server part
  378. // Runs gRPC server for GUI
  379. func (s *SnakeSimulator) StartServer() {
  380. go func() {
  381. grpcServer := grpc.NewServer()
  382. RegisterSnakeSimulatorServer(grpcServer, s)
  383. lis, err := net.Listen("tcp", "localhost:65002")
  384. if err != nil {
  385. fmt.Printf("Failed to listen: %v\n", err)
  386. }
  387. fmt.Printf("Listen SnakeSimulator localhost:65002\n")
  388. if err := grpcServer.Serve(lis); err != nil {
  389. fmt.Printf("Failed to serve: %v\n", err)
  390. }
  391. }()
  392. go s.remoteControl.Run()
  393. }
  394. // Steaming of Field updates
  395. func (s *SnakeSimulator) Field(_ *None, srv SnakeSimulator_FieldServer) error {
  396. ctx := srv.Context()
  397. for {
  398. select {
  399. case <-ctx.Done():
  400. return ctx.Err()
  401. default:
  402. }
  403. s.snakeReadMutex.Lock()
  404. srv.Send(s.field)
  405. s.snakeReadMutex.Unlock()
  406. <-s.fieldUpdateQueue
  407. }
  408. }
  409. // Steaming of Snake position and length updates
  410. func (s *SnakeSimulator) Snake(_ *None, srv SnakeSimulator_SnakeServer) error {
  411. ctx := srv.Context()
  412. for {
  413. select {
  414. case <-ctx.Done():
  415. return ctx.Err()
  416. default:
  417. }
  418. srv.Send(s.snake)
  419. <-s.snakeUpdateQueue
  420. }
  421. }
  422. // Steaming of snake simulator statistic
  423. func (s *SnakeSimulator) Stats(_ *None, srv SnakeSimulator_StatsServer) error {
  424. ctx := srv.Context()
  425. for {
  426. select {
  427. case <-ctx.Done():
  428. return ctx.Err()
  429. default:
  430. }
  431. s.fieldReadMutex.Lock()
  432. srv.Send(s.stats)
  433. s.fieldReadMutex.Unlock()
  434. <-s.statsUpdateQueue
  435. }
  436. }
  437. // Setup new speed requested from gRPC GUI client
  438. func (s *SnakeSimulator) SetSpeed(ctx context.Context, speed *Speed) (*None, error) {
  439. s.speedQueue <- speed.Speed
  440. return &None{}, nil
  441. }
  442. // Ask to play requested from gRPC GUI client
  443. func (s *SnakeSimulator) PlayBest(ctx context.Context, _ *None) (*None, error) {
  444. s.isPlaying = true
  445. s.isPlayingUpdateQueue <- s.isPlaying
  446. return &None{}, nil
  447. }
  448. // Play in loop
  449. func (s *SnakeSimulator) PlayBestInLoop(_ context.Context, playBest *PlayingBestState) (*None, error) {
  450. s.repeatInLoop = playBest.State
  451. return &None{}, nil
  452. }
  453. // State of playing
  454. func (s *SnakeSimulator) IsPlaying(_ *None, srv SnakeSimulator_IsPlayingServer) error {
  455. ctx := srv.Context()
  456. for {
  457. select {
  458. case <-ctx.Done():
  459. return ctx.Err()
  460. default:
  461. }
  462. srv.Send(&PlayingBestState{
  463. State: s.isPlaying,
  464. })
  465. <-s.isPlayingUpdateQueue
  466. }
  467. }