Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- with Ada.Text_Io, Plateau, Configs, TableHach, File,
- Ada.Unchecked_Deallocation ;
- use Ada, Ada.Text_Io, Plateau, Configs, TableHach ;
- function CheminGagnant return ConfigConnue is
- procedure Deallocate is new Unchecked_Deallocation(ConfigCell,
- ConfigConnue) ;
- -- current Etat/Config
- InitConfig: constant Config := Exporte_Etat ;
- ---- an irrelevant Coup used to instantiate the initial ConfigConnue
- --C: Coup;
- -- pointing to the currently checked Config (head of queue)
- CurrentConf: ConfigConnue ;
- -- Adds all the neigbours of the given Config into the queue.
- procedure AddNeighbours(CurrentConf: in ConfigConnue) is
- -- represent all the moves which can be played one after the other
- -- (and thus the reachable neighbour Configs)
- TempECoup: Enum_Coup ;
- -- the current neighbour's Config
- NeighbourConfig: Config ;
- begin
- -- get the first usable move
- Demarrer(TempECoup) ;
- -- while there is a next possible move, add the related Config
- -- into the queue
- while (not Fin(TempECoup)) loop
- -- get the Config of the current move
- Effectue(Courant(TempECoup)) ;
- NeighbourConfig := Exporte_Etat ;
- -- if this Config is not already in the hash table, add it
- -- (this avoids adding to many elements in the File, but is not
- -- a sufficient condition to filter all the irrelevant ones)
- if (Cherche(NeighbourConfig) = null) then
- File.Inserer(new ConfigCell'
- (NeighbourConfig, CurrentConf,
- Courant(TempECoup), null)) ;
- end if ;
- -- set the board to the previous position
- Met_Plateau(CurrentConf.all.Clef) ;
- -- get the next possible move
- Avancer(TempECoup) ;
- end loop ;
- end AddNeighbours ;
- begin
- File.Vider ;
- -- insert the initial Etat into the queue as its first element
- CurrentConf := new ConfigCell ;
- CurrentConf.Clef := InitConfig ;
- File.Inserer(CurrentConf) ;
- -- Each iteration is associated with a unique Config (Etat).
- -- The first element of the queue is added into the hash table, and
- -- each one of its neighbours is then added into the Queue unless
- -- they are already existing in the hash table, or unless the current
- -- queue head is a winning Config.
- while (not File.Estvide) loop
- -- get the head of the queue (the currently checked Config)
- File.Extraire(CurrentConf) ;
- if (TableHach.Cherche(CurrentConf.all.Clef) = null) then
- -- set the board to the current Config
- Met_Plateau(CurrentConf.all.Clef) ;
- -- insert the head of the queue into the hash table
- TableHach.Inserer(CurrentConf) ;
- -- check if the added Config is a winning one
- if (Plateau.A_Gagne) then
- -- if it is, set the board back to the initial Config
- Plateau.Met_Plateau(InitConfig) ;
- File.Vider ;
- -- complete the hash table and return the initial Config
- return TableHach.SetWinningConfig(CurrentConf) ;
- end if ;
- -- add the relevant neighbours of the current Config
- AddNeighbours(CurrentConf) ;
- else
- Deallocate(CurrentConf) ;
- end if;
- end loop ;
- -- reaching this code part means no winning Config has been found
- Met_Plateau(InitConfig) ;
- File.Vider ;
- return null ;
- end ;
Add Comment
Please, Sign In to add comment