CN109615074B - Method and device for generating monster configuration of game - Google Patents
Method and device for generating monster configuration of game Download PDFInfo
- Publication number
- CN109615074B CN109615074B CN201811534241.9A CN201811534241A CN109615074B CN 109615074 B CN109615074 B CN 109615074B CN 201811534241 A CN201811534241 A CN 201811534241A CN 109615074 B CN109615074 B CN 109615074B
- Authority
- CN
- China
- Prior art keywords
- checkpoint
- gene
- individual
- monster
- genetic
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 71
- 108090000623 proteins and genes Proteins 0.000 claims abstract description 198
- 230000002068 genetic effect Effects 0.000 claims abstract description 93
- 238000004422 calculation algorithm Methods 0.000 claims abstract description 15
- 238000004364 calculation method Methods 0.000 claims abstract description 8
- 238000012216 screening Methods 0.000 claims abstract description 5
- 230000006870 function Effects 0.000 claims description 46
- 238000011156 evaluation Methods 0.000 claims description 25
- 239000008280 blood Substances 0.000 claims description 19
- 210000004369 blood Anatomy 0.000 claims description 19
- 230000035772 mutation Effects 0.000 claims description 10
- 238000003860 storage Methods 0.000 claims description 7
- 238000009826 distribution Methods 0.000 claims description 6
- 239000011159 matrix material Substances 0.000 claims description 6
- 238000004590 computer program Methods 0.000 claims description 4
- 238000010276 construction Methods 0.000 claims description 3
- 230000007123 defense Effects 0.000 description 14
- 230000008569 process Effects 0.000 description 13
- 238000013461 design Methods 0.000 description 11
- 238000004519 manufacturing process Methods 0.000 description 7
- 241000894007 species Species 0.000 description 6
- 230000008859 change Effects 0.000 description 5
- 241000282414 Homo sapiens Species 0.000 description 4
- 210000000349 chromosome Anatomy 0.000 description 4
- 230000014509 gene expression Effects 0.000 description 4
- 230000004048 modification Effects 0.000 description 4
- 238000012986 modification Methods 0.000 description 4
- 238000012360 testing method Methods 0.000 description 3
- 230000004075 alteration Effects 0.000 description 2
- 230000004888 barrier function Effects 0.000 description 2
- 230000008901 benefit Effects 0.000 description 2
- 230000005540 biological transmission Effects 0.000 description 2
- 238000010586 diagram Methods 0.000 description 2
- 238000013507 mapping Methods 0.000 description 2
- 238000010606 normalization Methods 0.000 description 2
- 101150090724 3 gene Proteins 0.000 description 1
- 230000006978 adaptation Effects 0.000 description 1
- 238000013459 approach Methods 0.000 description 1
- 101150010487 are gene Proteins 0.000 description 1
- 238000013473 artificial intelligence Methods 0.000 description 1
- 239000000969 carrier Substances 0.000 description 1
- 238000006243 chemical reaction Methods 0.000 description 1
- 238000005094 computer simulation Methods 0.000 description 1
- 239000000470 constituent Substances 0.000 description 1
- 230000003631 expected effect Effects 0.000 description 1
- 238000002474 experimental method Methods 0.000 description 1
- 239000012634 fragment Substances 0.000 description 1
- 230000008303 genetic mechanism Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 230000037361 pathway Effects 0.000 description 1
- 102000004169 proteins and genes Human genes 0.000 description 1
- 230000000717 retained effect Effects 0.000 description 1
- 230000000638 stimulation Effects 0.000 description 1
- 230000004083 survival effect Effects 0.000 description 1
- 230000002123 temporal effect Effects 0.000 description 1
- 230000009466 transformation Effects 0.000 description 1
- 239000011800 void material Substances 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/12—Computing arrangements based on biological models using genetic models
- G06N3/123—DNA computing
-
- A—HUMAN NECESSITIES
- A63—SPORTS; GAMES; AMUSEMENTS
- A63F—CARD, BOARD, OR ROULETTE GAMES; INDOOR GAMES USING SMALL MOVING PLAYING BODIES; VIDEO GAMES; GAMES NOT OTHERWISE PROVIDED FOR
- A63F13/00—Video games, i.e. games using an electronically generated display having two or more dimensions
- A63F13/60—Generating or modifying game content before or while executing the game program, e.g. authoring tools specially adapted for game development or game-integrated level editor
-
- A—HUMAN NECESSITIES
- A63—SPORTS; GAMES; AMUSEMENTS
- A63F—CARD, BOARD, OR ROULETTE GAMES; INDOOR GAMES USING SMALL MOVING PLAYING BODIES; VIDEO GAMES; GAMES NOT OTHERWISE PROVIDED FOR
- A63F13/00—Video games, i.e. games using an electronically generated display having two or more dimensions
- A63F13/80—Special adaptations for executing a specific game genre or game mode
- A63F13/822—Strategy games; Role-playing games
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/12—Computing arrangements based on biological models using genetic models
- G06N3/126—Evolutionary algorithms, e.g. genetic algorithms or genetic programming
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Life Sciences & Earth Sciences (AREA)
- Biophysics (AREA)
- Health & Medical Sciences (AREA)
- Bioinformatics & Cheminformatics (AREA)
- Bioinformatics & Computational Biology (AREA)
- Evolutionary Biology (AREA)
- Multimedia (AREA)
- Theoretical Computer Science (AREA)
- Data Mining & Analysis (AREA)
- General Engineering & Computer Science (AREA)
- Biomedical Technology (AREA)
- Evolutionary Computation (AREA)
- General Health & Medical Sciences (AREA)
- Molecular Biology (AREA)
- Computing Systems (AREA)
- Computational Linguistics (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Software Systems (AREA)
- Artificial Intelligence (AREA)
- Genetics & Genomics (AREA)
- Physiology (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
The invention relates to a method and a device for generating configuration of monsters of a game, wherein the method comprises the following steps: constructing a gene pool; generating a plurality of checkpoint genotype representations based on the gene segments in the gene pool; generating a preliminary population comprising genetic checkpoint individuals based on the plurality of checkpoint genotype representations; a fitness calculation step, namely calculating the fitness of each gene checkpoint individual by using a fitness function; an individual selection step: determining whether available gene level individuals exist or not based on the calculated fitness of each gene level individual, and screening out parent gene level individuals from the initial population based on the calculated fitness of each gene level individual under the condition of no; an evolution step: generating a population of a new generation of genetic checkpoint individuals by utilizing a genetic algorithm based on the parent genetic checkpoint individuals; and repeating the fitness calculation step, the individual selection step and the evolution step until the existence of the available gene checkpoint individuals is determined based on the calculated fitness of each gene checkpoint individual, and outputting the available gene checkpoint individuals.
Description
Technical Field
The invention relates to the technical field of artificial intelligence, in particular to a method and a device for generating configuration of monsters of games.
Background
The tower defense game refers to a strategy game for defending the own party to run on the earth by building a gun tower or similar buildings on a map to attack and block enemies from advancing. Tower defense games are enjoyed by players because they are characterized by increased difficulty, increased excitement, and more challenging for the players as the game progresses.
In the tower defense game, a strange configuration determines the difficulty and the playability of the whole stage. An overly difficult level can frustrate a player's interest, while a simpler level can be unattractive to the player because it is not challenging. In addition, different combinations of monsters can bring more freshness to the game. Therefore, the generation of rich and interesting level-of-difficulty level is a crucial link in the design of the tower defense game.
At present, monster generation for tower defense games is commonly generated using manually configured methods. The manual configuration method is that related plans with professional knowledge and designers participate to design strange schemes in the game level in advance, and the expected effect is achieved through manual repeated testing, continuous debugging and modification and difficulty adjustment. This is the most straightforward approach to design a scenario. Because of the adoption of manual configuration, the traditional tower defense game strange design needs a plurality of manual work types to be matched with each other, and needs manual repeated adjustment and test. Such designs are often inefficient, the design time for a strange scheme is often lengthy, which undoubtedly requires the consumption of a large amount of manpower and other resources, greatly reduces the efficiency of overall game production, and the excessively high design cost greatly limits the playable time of a tower defense game.
How to rapidly and automatically generate monster configuration under the condition of ensuring the common characteristics of tower defense games, achieve the aims of improving the game production capacity and reducing the manpower input and the fund input, and ensure the interest and the stimulation of the games is a technical problem to be solved.
Disclosure of Invention
Embodiments of the present invention are proposed in view of the above problems in the prior art, and aim to provide a method and an apparatus for generating a monster configuration of a game, so as to solve one or more disadvantages in the prior art, and to provide at least one useful choice.
The technical scheme of the invention is as follows:
according to an aspect of the invention, there is provided a monster configuration generation method for a game, the method comprising the steps of:
a gene pool construction step: constructing at least one gene pool comprising a plurality of monster configuration gene segments, wherein the gene segments comprise gene numbers and monster gene information, and the monster gene information comprises monster matrix type information;
checkpoint genotype representation generation step: generating a plurality of checkpoint genotype representations based on gene segments in the gene pool, each checkpoint genotype representation including monster wave information, path information corresponding to each wave, and gene representations of monsters on each path corresponding to each wave, wherein the gene representations of monsters on each path corresponding to each wave include gene segment placeholder sequences of a particular length;
generating a primary population: generating a preliminary population comprising a predetermined number of genetic checkpoint individuals based on the plurality of checkpoint genotype representations;
and a fitness calculation step: calculating the fitness of each gene checkpoint individual in the currently generated population;
an individual selection step: determining whether available genetic checkpoint individuals exist or not based on the calculated fitness of each genetic checkpoint individual, and screening out a predetermined proportion or number of genetic checkpoint individuals from the current population as parent genetic checkpoint individuals based on the calculated fitness of each genetic checkpoint individual under the condition that no available genetic checkpoint individual exists;
an evolution step: generating a population of a new generation of genetic checkpoint individuals by utilizing a genetic algorithm based on the parent genetic checkpoint individuals;
and repeating the fitness calculating step, the individual selecting step and the evolving step until the existence of the available genetic checkpoint individuals is determined based on the calculated fitness of each genetic checkpoint individual, outputting the available genetic checkpoint individuals, and generating a monster configuration based on the output genetic checkpoint individuals.
Preferably, the generating a monster configuration for the output-based genetic checkpoint individual comprises: generating a strange configuration in a checkpoint profile based on the outputted checkpoint genotype representation for the genetic checkpoint individual.
Preferably, the strange configuration in the checkpoint profile further comprises at least one of the following configuration parameters: the number of the monsters, the blood volume of the monsters, the number of the monsters and the density of the monsters; the method further comprises the following steps: and evaluating strange configurations in the level configuration file by using the configuration parameters.
Preferably, the method further comprises: at least one configuration parameter in the strange configuration is adjusted, and the optimal strange configuration is selected based on the adjusted evaluation result.
Preferably, prior to the step of constructing a gene pool, the method further comprises: a plurality of monster configuration gene segments are generated based on configuration data of the original checkpoint.
Preferably, the step of generating a plurality of monster configuration gene segments based on the configuration data of the original checkpoint comprises: and splitting the configuration data of each wave of monsters in the original checkpoint according to the paths, and generating a plurality of monster configuration gene segments based on the occurrence time intervals and distribution among the monsters on each path.
Preferably, the information elements in the monster configuration gene segments, the information elements in the checkpoint genotype representation, and/or the gene segment placeholder sequences of a particular length are configured in a list format.
Preferably, the constructed at least one gene pool is a plurality of segmented gene pools respectively corresponding to different checkpoint levels or different monster bands.
Preferably, the gene segment placeholder sequences in the checkpoint genotype representation are generated by random placeholder of gene segments in the corresponding gene pool.
Preferably, the step of generating a preliminary population of a predetermined number of genetic checkpoint individuals based on the plurality of checkpoint genotype representations comprises: expressing the gene level genotypes of a predetermined number as gene level individuals of a predetermined number, and generating a gene level individual primary population; or generating a preliminary population of a predetermined number of genetic checkpoint individuals using a plurality of checkpoint genotype representations and genetic codes configured to indicate whether there is a monster on each primary path of each wave in the current checkpoint.
Preferably, calculating the fitness of each individual genetic checkpoint in the currently generated population comprises: calculating the fitness of each gene checkpoint individual in the currently generated population by using a fitness function; the fitness function is a fitness function determined based on at least one of the following parameters: monster number, monster species, monster blood volume, and monster density.
Preferably, the fitness function formula is three functions f N 、f T，T′ And f H In which f is N F is a function for measuring the similarity of the current genetic checkpoint individual and the reference checkpoint individual based on the number of monsters T，T′ F is a function representing the similarity of the current genetic checkpoint individual to the reference checkpoint individual measured based on the category of monsters H Is a function representing the measure of similarity of the current genetic checkpoint individual to the reference checkpoint individual based on the monster blood volume.
Preferably, f N ＝d 1 (N c ，N r )+d 2 (N c ，N r )+|∑N c +∑N r |；
f T，T′ ＝θ 1 d 1 (T c ，T r )+θ 2 |T c ′-T r ′|；
f ti ＝θ 3 d 1 (H e ，H r )+θ 4 d 2 (H c ，H r )；
Where Nc and Nr represent the number of monsters appearing in each wave for the current genetic checkpoint and the reference checkpoint, respectively, tc and Tr represent the number of types of monsters appearing in each wave for the current genetic checkpoint and the reference checkpoint, respectively, hc and Hr represent the sum of blood volumes of monsters appearing in each wave for the current genetic checkpoint and the reference checkpoint, respectively, and function d 1 Calculating a function for the Manhattan distance, function d 2 For cosine similarity calculation function, theta 1 ，θ 2 ，θ 3 ，θ 4 Respectively, are weight coefficients.
Preferably, the step of evolving comprises: and (3) carrying out cross operation and/or mutation after disorder on the parent gene checkpoint individual population to generate a new gene checkpoint individual, thereby generating a new generation gene checkpoint individual population comprising the new gene checkpoint individual and part or all of the parent gene checkpoint individual.
According to another aspect of the present invention there is also provided a monster configuration generating device for a game, the device comprising a processor and a memory, the memory for storing computer instructions, the processor for executing the computer instructions stored in the memory, the monster configuration generating device implementing the steps of the method as described above when the processor executes the computer instructions stored in the memory.
According to another aspect of the present invention, there is also provided a computer readable storage medium having stored therein a computer program which, when executed by a processor, implements the steps of the method as described above.
The method and the device for generating the monster configuration of the game can generate the monster configuration by using a computer, and can automatically generate the game level with moderate difficulty and rich content through the constraint of a fitness (fitness) function. And the subsequent stage of barrier configuration is free from manual participation, so that the manpower resource is greatly saved, and the production efficiency of the tower defense game is greatly improved.
It will be appreciated by those skilled in the art that the objects and advantages that can be achieved with the present invention are not limited to the specific details set forth above, and that these and other objects that can be achieved with the present invention will be more clearly understood from the detailed description that follows.
Drawings
The above and other objects, features and advantages of the present invention will be more readily understood by reference to the following description of the embodiments of the present invention taken in conjunction with the accompanying drawings.
FIG. 1 is a flow chart of a monster configuration generation method in an embodiment of the present invention.
FIG. 2 is an example of a matrix of a wave monster in accordance with an embodiment of the present invention.
FIG. 3 is a schematic illustration of the genetic representation of a monster in the representation of checkpoint genotypes, in accordance with an embodiment of the present invention.
Fig. 4 is a curve of the fitness variation of each generation of individual checkpoint with respect to the reference checkpoint in an embodiment of the present invention.
FIG. 5 is a representation of normalized fitness value according to an embodiment of the present invention.
FIG. 6 is a flow chart of a method for generating configuration of monsters in another embodiment of the present invention.
FIG. 7 is a graph comparing the four dimensions of the evaluated level with the original level according to one embodiment of the present invention.
FIG. 8 is a graph illustrating the percentage of change in the four dimensions of the assessed level relative to the original level in accordance with an embodiment of the present invention.
Fig. 9 is a graph showing the sum of the percentages of the four dimensions in fig. 8.
FIG. 10 is a comparison of the estimated checkpoint monster density after adjustment with the original checkpoint in accordance with an embodiment of the present invention.
FIG. 11 is a flowchart illustrating a method for generating a monster configuration in an embodiment of the invention.
Fig. 12 is a schematic diagram of a hardware structure for implementing the method for generating a monster configuration according to an embodiment of the present invention.
Detailed Description
Embodiments of the present invention will be described below with reference to the drawings. In the description and drawings, particular embodiments of the invention have been disclosed in detail as being indicative of the manner in which the principles of the invention may be employed. It will nevertheless be understood that no limitation of the scope of the invention is thereby intended. The invention includes many variations, modifications and equivalents within the spirit and scope of the appended claims.
It should be noted that the figures and description omit representation and description of components and processes that are not relevant to the present invention and that are known to those of ordinary skill in the art for the sake of clarity.
Features that are described and/or illustrated with respect to one embodiment may be used in the same way or in a similar way in one or more other embodiments, in combination with or instead of the features of the other embodiments.
It should be emphasized that the term "comprises/comprising" when used herein, is taken to specify the presence of stated features, elements, steps or components, but does not preclude the presence or addition of one or more other features, elements, steps or components.
The present invention combines human intelligence with machine intelligence. The basic idea is that human beings design a plurality of small fixed strange patterns (for example, the fixed strange patterns can be from the configuration data of the original checkpoint) as gene segments, and then combine the small strange patterns (gene segments) into a strange pattern of a wave, and evolve reasonable strange configurations through genetic algorithm. Further, the generated strange configuration can be evaluated through multiple dimensions (such as multiple evaluation parameters), and adjusted according to the evaluation result.
Genetic Algorithm (Genetic Algorithm) is a computational model of the biological evolution process that simulates the natural selection and Genetic mechanism of darwinian biological evolution theory, and is a method for searching for an optimal solution by simulating the natural evolution process. Genetic algorithms start with a population (population) representing a possible potential solution set to the problem, and a population consists of a certain number of individuals (individual) encoded by genes (gene). Each individual is actually an entity with a characteristic of the chromosome (chromosome). Chromosomes, which are the main carriers of genetic material, are collections of genes whose internal expression (i.e., genotype) is a certain combination of genes that determines the external expression of an individual's shape, e.g., black hair, whose characteristics are determined by the certain combination of genes in the chromosome that control this characteristic. Therefore, mapping from phenotype to genotype, i.e., coding work, needs to be achieved in the beginning. Since the work of imitating gene codes is complex, simplification is often needed, such as simplification by using binary codes, generation-by-generation evolution generates better and better approximate solutions according to the principle of survival and preference of fittest after the generation of initial generation populations, and in each generation, individuals are selected (selection) according to the fitness (fitness) of individuals in a problem domain, and a population representing a new solution set is generated by crossing (cross) and variation (mutation) through genetic operators of natural genetics. This process will cause the population of the next generation, like natural evolution, to be more environment-adaptive than the previous generation, and the optimal individuals in the population of the last generation can be decoded (decoding) as a near-optimal solution to the problem.
The invention utilizes genetic algorithm to automatically generate a large number of tower defense game odd configurations, however, the invention is not only suitable for tower defense games, but also suitable for games needing odd configurations.
FIG. 1 is a flow chart of a monster configuration generation method in an embodiment of the present invention, as shown in FIG. 1, the method includes the following steps:
step S110, gene pool construction.
This step is for constructing at least one gene pool comprising a plurality of monster configuration gene segments.
To construct a gene pool, a plurality of monster configuration gene segments may first be constructed. The gene segments may include gene numbers and monster gene information, wherein the monster gene information includes monster matrix type information.
In one embodiment, existing monster patterns may be extracted from the original game stage using the designer's wisdom of a portion of the original stage, and the existing monster patterns may be used as monster configuration gene segments. For example, the configuration data of the original level can be traversed, the configuration data of each wave in the original level can be split according to the path, and the occurrence time and distribution of monsters on each path can be counted. When several monsters appear in succession on the same path, i.e., the interval between every two monsters is less than a threshold, such as 300 frames, the monsters are taken as a gene segment together with the interval between them and the distribution on their respective paths. Thus, a monster can be separated into multiple gene segments. Here, the threshold value for the time interval between monsters is used to divide monsters in each wave that are spaced too far apart into different segments to facilitate flexible mapping in subsequent monster configurations. Here, the 300 frames are merely examples, and the present invention is not limited thereto. Preferably, when the path in the game interface of the level is wide, each wide main path may be divided into 2 or more sub-paths, for example, the main path may be divided into 3 sub-paths in upper, middle and lower positions of the main path according to monsters. FIG. 2 shows an example of a matrix of a wave monster in an embodiment of the present invention. In fig. 2, the monsters appearing in the way all belong to a wave and all walk one way. But it is clear that they can be divided into three segments. Thus, each segment can be used as a gene segment (i.e., gene segment) in the gene pool, and the number is 1,2,3, and the gene information in the gene segment can include the spacing and the positions of the monsters in the particular segment. Because on a main path, a monster can walk on the upper side or the lower side of the path, and can also walk in the middle of the path, the upper, middle and lower positions of the main path are respectively equivalent to 3 sub-paths of the main path. Thus, gene fragments may retain temporal, positional, or, in other words, monster matrix information.
The generation of gene segments using monster configurations of the original checkpoint was described above. In another embodiment of the present invention, the gene pool can also be constructed by redesigning the gene segments.
In the preferred embodiment of the present invention, a gene segment may be in the form of a list, and each element in the list may also be a list indicating what is strange at a moment. The first element in the gene segment may represent time and the second element may be a dictionary listing, which may be structured, for example, to correspond to a key in the waves-events configuration in the original checkpoint configuration. The reason why the storage is not completely as original is to convert the storage into a list form, which is to facilitate the subsequent sequential traversal operation to be used.
The constructed gene segment can be used to construct a gene pool, and as an example, the gene pool can be a dictionary, the key is the number of the gene segment, and the value is the gene information of the gene segment.
In a preferred embodiment of the present invention, in order to make the newly generated checkpoint closer to the original checkpoint, a plurality of segmented gene pools may be constructed, each of which may correspond to a different checkpoint level or a different monster band, respectively. This is because, in the game, the types and the amounts of the monsters appearing in the early stage and the later stage of the different level are greatly different, and the building of the segmented gene pool according to the level of the level or the band of the monsters can avoid the big monsters appearing in the later stage of the early stage of the game. As an example, 3 gene pools can be constructed, the first gene pool can be constructed for the first 1 st to 5 th wave monsters, the second gene pool can be constructed for the middle 6 th to 10 th wave monsters, and the third gene pool can be constructed for the later 11 th to 15 th wave monsters, so that each wave monster configuration selects only genes (gene segments) from the corresponding gene pool when generating new checkpoints. In addition, a plurality of segmented gene pools can also be constructed based on different level cards, for example, a gene segment corresponding to a first level card is constructed for the first time, namely N times, a gene segment corresponding to a second level card is constructed for the second level card, and a gene segment corresponding to a third level card is constructed for the third level card.
Step S120, checkpoint genotype representation generation step: a plurality of checkpoint genotype representations are generated based on the gene segments in the constructed gene pool.
Preferably, a checkpoint genotype representation can be represented as a list, each element in the list representing data of a wave, each wave being in turn a list, each element in the list being data on one path (this path being the main path), data on one path (gene segment placeholder sequence of a certain length) being a list, each element being a value representing one gene in the gene pool. The length of the list of path data is a predetermined fixed value, such as 20, where a gene value of 0 represents a gap. Examples of checkpoint genotype representations are as follows:
<xnotran> [ [ 1[1,0,10,9,19,0,0,0,19,0,0,2,15,0,0,0,6,0,0,11], 2[10,0,9,0,4,0,0,16,12,0,0,0,0,8,0,7,0,5,0,9] ], </xnotran>
The second wave [. Yet. ],
...
]
a level contains a plurality of waves, and each wave is divided according to different paths. For genes with a monster appearing on one path, such as the monster appearing on the first path in the first wave, 1, 10,9,19, etc. are gene numbers, corresponding to different monster segments in the gene pool. As shown in this example, each checkpoint genotype representation may include monster wave information, path information corresponding to each wave, and gene representations of monsters on each path corresponding to each wave, where the gene representations of monsters on each path corresponding to each wave include a gene segment placeholder sequence of a particular length.
FIG. 3 is a schematic representation of the configuration of wave 1 in the above tabular checkpoint genotype representation.
In the genetic algorithm to be described later, since the genes of each checkpoint individual are subjected to operations such as crossover and/or mutation, the length of the gene representation of each path of each wave in the gene representation of each checkpoint needs to be the same (set as the fixed path data length 20 as before), but actually the number of genes (monster segments) appearing on each path is not necessarily so large, and therefore, some void elements (0) need to be filled in to play a role of placeholder. These empty elements of the placeholders have no relation to the strange time interval. In the subsequent mutation step, some placeholder elements may be mutated to a non-0 genotype of practical significance, and some non-0 genotypes may also be mutated to 0. Thus, the use of placeholder element (0) in the gene representation may increase the likelihood of occurrence of the mutation.
In an embodiment of the present invention, the gene segment placeholder sequence of each pathway in the checkpoint genotype representation is generated by randomly extracting the gene segments in the corresponding gene pool and performing placeholder. For example, for each path in the checkpoint genotype representation, genes may be randomly selected from the corresponding gene pool, the selected gene codes randomly place bits in a length-20 list, and the remaining positions are all filled with 0. Each path in each wave may be generated as such. An individual may be initially generated.
Before each checkpoint is generated, it is possible to determine how many waves and how many main paths there are to be generated, whereby the genotype representation of the checkpoint is randomly generated by randomly occupying gene segments to generate a gene segment occupying sequence for each path.
Step S130, primary generation population generation step: generating a preliminary population including a predetermined number of genetic checkpoint individuals based on the plurality of checkpoint genotype representations.
As an example, the genotype representation for each level can be directly initialized to one genetic level individual, whereby a predetermined number (e.g., 1000) of level genotype representations can be made as a predetermined number of genetic level individuals to form an initial generation population of genetic level individuals.
As another example, a gene mask may be introduced to indicate whether there is a strangeness on the respective main path of each wave in the current checkpoint. A predetermined number of genetic checkpoint individual primary populations can be generated at this time using a plurality of checkpoint genotype representations and genetic codes. The reason for introducing a genetic mask is because, in some cases, similar to the original checkpoint configuration, it may be necessary for certain paths to be odd after a particular wavenumber, and introducing a genetic mask may determine which paths at which wavenumbers may be odd. The gene mask is a list, each element in the list represents data of a wave, and each wave is a list, wherein each element represents whether a strange occurs on a corresponding path (main path), 0 represents no strange, and 1 represents a strange. Table 1 below is an example of a gene mask:
table 1.
Gene mask =
[ first wave [0,1,0],
a second wave [1,1,1].
...
]
Table 1 shows that the first wave [0,1,0] does not strange about the first wave for main path No. 0 (corresponding to sub-path No. 0,1,2), main path No. 1 (corresponding to sub-path No. 3,4,5) and main path No. 2 (corresponding to sub-path No. 6,7,8).
Using multiple checkpoint genotype representations, in conjunction with a gene mask, a predetermined number (e.g., 1000) of genetic checkpoint individuals can be generated and from this, an initial generation population of genetic checkpoint individuals can be formed.
Step S140, a fitness calculation step: and calculating the fitness of each gene checkpoint individual in the currently generated population by using a fitness function.
And under the condition that the currently generated population is the initial generation population, the fitness of each gene checkpoint individual in the initial generation population is calculated in the step. For the offspring population, the fitness of each genetic checkpoint individual in the offspring population can also be calculated in this step, and the process of obtaining the offspring population through a genetic algorithm will be described later.
The fitness function is an evaluation function for simulating the adaptation degree of individual organisms to the environment in the biological evolution. The evaluation function of the generated individual genetic checkpoint is referred to in the invention, and the evaluation function is also a constraint function. The difficulty for constraining a new level from multiple dimensions makes it playable.
In the method of the embodiment of the invention, the quality of the generated individual gene level can be evaluated by measuring the similarity between the generated individual gene level and the reference level Sref (the reference level is taken from the original game or the standard is fitted by a regression method), namely the adaptability of the individual gene level is evaluated. The fitness function may measure how similar the current genetic checkpoint individual is to the reference checkpoint from a number of perspectives, for example, one or more of the number of monsters, category of monsters, blood volume of monsters, and density of monsters, although the invention is not limited in this respect. As an example, the fitness function measures how similar the current genetic checkpoint individual is to the reference checkpoint from three dimensions (number of monsters, category of monsters, blood volume of monsters):
1. the amount of monsters: the number of monsters in each wave for the current gene checkpoint individual and the reference checkpoint is denoted by Nc and Nr, respectively. Nc and Nr are both in the form of lists, each element in the list representing the number of monsters in the corresponding wave.
2. Species of monsters: the number of species in each wave in which the monster occurred in the current gene checkpoint individual and the reference checkpoint is represented by Tc and Tr, respectively. Tc and Tr are both in the form of a list, each element of which represents the number of monster species in the corresponding wave. In addition, tc ' and Tr ' may be used to represent the number of odd species present in the entire checkpoint, respectively, and Tr ' is not the sum of the elements in the list Tr, since there will be repeat species present.
3. Blood volume of monster: hc and Hr represent the sum of the blood volume of the current gene checkpoint individual and the reference checkpoint, respectively, with the appearance of monsters in each wave. Hc and Hr are both in the form of lists, each element in the list representing the sum of the blood volume of monsters in the corresponding wave.
In one embodiment of the present invention, two functions d may be used 1 () And d 2 () To measure gene level individuals against reference levelsDegree of similarity, wherein the function d 1 () Calculating a function for the Manhattan distance, function d 2 () A function is calculated for cosine similarity, for example:
d 1 () And d 2 () The two functions are applied in measuring the degree of similarity in different dimensions as follows:
f N ＝d 1 (N c ，N r )+d 2 (N c ，N r )+|∑N c +∑N r | (4)
f T，T’ ＝θ 1 d 1 (T c ，T r )+θ 2 |T c ′-T r ′| (5)
f H ＝θ 3 d 1 (H o ，H r )+θ 4 d 2 (H o ，H r ) (6)
wherein, theta 1 ，θ 2 ，θ 3 ，θ 4 Respectively, are weight coefficients. The overall fitness function may be a linear combination of the three functions:
fitness＝af N +bf T，T′ +cf H (7)
wherein, a, b and c are respectively systems, which can be the same or different.
In an embodiment of the present invention, the performance of the fitness value after normalizing the fitness values of all individuals in each generation of population can also be calculated. The normalization method comprises the following steps:
wherein, mu and sigma respectively represent the mean value and standard deviation of each characteristic dimension fitness value set of all individuals in the generation group, and the normalized individual fitness value is the sum of normalized values on each dimension of the individual. The normalized value ranges from (-1, + 1), and thus the value ranges from (-3, + 3).
FIG. 4 is a curve illustrating the fitness of each generation of level individual relative to a reference level in accordance with an embodiment of the present invention. As shown in fig. 4, the horizontal axis represents the evolution algebra and the vertical axis represents the fitness. Since the fitness for the candidate sequence is calculated by comparing the degree of similarity with the reference level, the lower the fitness value, the better, as shown in the left figure. The fitness substantially converges after about 175 generations.
FIG. 5 is a representation of normalized fitness value according to an embodiment of the present invention. As shown in fig. 5, a higher value indicates that the individual has a higher adaptability in the current population and is more likely to be retained. The curve as a whole therefore tends to rise. In practical experiments, the whole evolution process can be accelerated by screening individuals by using the normalized fitness value.
While fitness above measures the difficulty of the level from three dimensions, the invention is not so limited and may use more or fewer dimensions to generate a fitness function to measure the level.
And S150, determining whether available genetic checkpoint individuals exist or not based on the calculated fitness of each genetic checkpoint individual.
For example, for each genetic checkpoint individual in the primary population, it may be determined whether there are available genetic checkpoint individuals based on the fitness calculated in step S140. In one embodiment of the present invention, the available genetic checkpoint individuals refer to at least one genetic checkpoint individual whose fitness value satisfies a predetermined condition. The predetermined condition may be, for example, that the fitness value is less than a predetermined fitness threshold.
For offspring populations, it may also be determined whether there are available genetic checkpoint individuals based on the fitness calculated in step S140. At this time, the predetermined condition for determining that there are available genetic checkpoints individuals may be, for example, that the fitness value is less than a predetermined fitness threshold, or that the minimum fitness value among the fitness values of the individual continuously converges for a predetermined number of generations (e.g., converges for 10 consecutive generations).
Preferably, an individual with a genetic checkpoint that satisfies a predetermined condition and has a small fitness value can be selected as an available individual with a genetic checkpoint.
Step S160, individual selection step: and under the condition that no available gene level individuals exist, screening out a predetermined proportion or number of gene level individuals from the current population according to the calculated fitness of each gene level individual as parent gene level individuals.
For example, all individuals in the current population are sorted according to fitness, the top 20% of individuals are selected as parent genetic checkpoint individuals, and the population corresponding to the parent genetic checkpoint individuals is also referred to as the parent individual population. Here, 20% is merely an example, and the present invention is not limited thereto.
Step S170, an evolution step: and generating a population of the new generation of genetic checkpoint individuals by utilizing a genetic algorithm based on the parent genetic checkpoint individuals.
In embodiments of the present invention, the step of evolving may include crossover and/or mutation.
The interleaving operation may include: and (3) disorder is carried out on the parent gene checkpoint individuals in the parent individual population, the parent gene checkpoint individuals are equally divided into parents and mothers, and then the parents and the mothers are in one-to-one correspondence and crossed. At the time of crossing, a random number sequence is generated, some pieces of DNA which are selected from fathers as father contributions are selected from the fathers according to the random sequence, corresponding pieces which are not selected from the fathers (namely, pieces which are staggered with the pieces of the fathers) are obtained from mothers as mother contributions, and the two pieces of DNA are combined according to the original sequence to generate new individuals.
The mutation process is as follows: and selecting a certain gene segment on one path data for mutation at one time, randomly mutating the certain gene segment into one other value or 0, and not mutating the certain gene segment if the gene mask corresponding to the path is 0.
After the new generation of population of genetic checkpoint individuals is generated, the method returns to step S140, and fitness calculation is performed on each individual in the currently generated population.
In step S180, if it is determined that there is an available individual based on the calculated fitness, the available individual is output.
Step S190, performing gene expression of the individual: and converting the checkpoint representation into a standard checkpoint profile format based on the output genetic checkpoint individuals, in other words, generating odd configurations in the checkpoint profile based on the checkpoint genotype representation of the output genetic checkpoint individuals.
There are several points to be noted during the transformation:
1. odd time in individual gene segments has been converted to relative time, and when several gene segments are combined, it is converted to absolute time;
2. each strange path information in the gene segment is usually a path in the original level, new path information needs to be generated according to the current main path in the gene expression process, but the relative distribution among all sub-paths in the main path is reserved at all.
By the method, the game with the common characteristics of the tower defense game can be automatically and quickly generated by designing the automatic generation algorithm, the game interest and the exciting monster configuration can be effectively improved, a novel game design production form using a computer to replace personnel such as planning and designing in the traditional tower defense game production process is formed, and the purposes of improving the game production capacity and reducing the labor investment and the fund investment are achieved. The game level with moderate difficulty and rich content can be automatically generated through the constraint of the fitness function in the embodiment of the invention. And the subsequent stage of barrier configuration is free from manual participation, so that the manpower resource is greatly saved, and the production efficiency of the tower defense game is greatly improved.
FIG. 6 is a flow chart of a method for generating configuration of monsters in another embodiment of the present invention. In addition to the various steps S100-S190 shown in FIG. 1, there are additional monster configuration evaluation steps S200 and monster configuration adjustment steps S210 in this flowchart. Here, steps S100 to S190 will not be repeated, and only step S200 and step S210 will be described.
In step S200, the monster configuration of the level configuration generated in step S190 is evaluated.
In the embodiment of the present invention, the odd configuration in the gate configuration generated by step S190 may be evaluated by the evaluation parameters of multiple dimensions.
As an example, for a strange configuration among the customs configurations generated through the above step S190, the criteria for constructing a new customs can be compared through four dimensions. For example, 4 configuration parameters of the number of monsters, the blood volume of monsters, the number of monsters and the density of monsters can be selected as the evaluation dimension, and of course, more or less dimensions can be selected for evaluation. The monster density is the number of monsters present per unit time, calculated as the number of monsters per wave divided by the length of time the monsters appear (the time the last monster appears minus the time the first monster appears). When four dimensions are evaluated, the index value of each wave in the level is counted to obtain a sequence, then the sequence is compared with a target sequence, and the change percentage of the corresponding position number value is calculated, namely the increase or decrease percentage of the level compared with the target sequence is generated. And then summing all the absolute values of the percentages, and taking the obtained value as an evaluation value for generating the level. Assuming that the threshold for each percentage change of the corresponding value is 0.2 (or other values), and there are n-wave monsters generated, the evaluation sum is 0.2 × 4 × n.
FIG. 7 is a diagram illustrating a comparison of four dimensions of the evaluated level with the original level according to an embodiment of the present invention. FIG. 8 is a graph illustrating the percentage of change in the four dimensions of the assessed level relative to the original level in accordance with an embodiment of the present invention. Fig. 9 is a graph showing the sum of the percentages of the four dimensions in fig. 8. Fig. 7-9 may represent the checkpoint condition. In the evaluation test, 1-11 gates in the original gates are respectively referred, the method is used for generating corresponding 11 gates out odd sequences, and the map information such as the path, the tower pit and the like can use the information of the original map. In fig. 7, 4 sub-graphs (a), (b), (c), and (d) respectively show the numerical distributions of the generated 1-11 level and the original game 1-11 level in four dimensions, which are the total number of monsters ((a) in fig. 7), the total blood volume ((b) in fig. 7), the total prize number of all monsters ((c) in fig. 7), and the output density ((d) in fig. 7), in each sub-graph, the horizontal axis represents the level of the level, the vertical axis represents the numerical size of the corresponding feature of each level, the numerical changes of the original level are represented by dots, and the numerical changes of the new level generated by using the method of the present invention are represented by crosses. Fig. 8 shows the difference between the generated level and the original level in four dimensions, where the horizontal axis represents the level number and the vertical axis represents the difference value, i.e., the percentage value of the change. Fig. 9 shows the total evaluation value (evaluation score) of the newly generated level, the abscissa indicates the level number, and the ordinate indicates the evaluation value of the newly generated level, which is the sum of the absolute values of the percentages of changes from the original level in four dimensions.
It is obvious that the newly generated results are very similar to the original checkpoint in the three dimensions of the total number of monsters, the total blood volume and the total reward, because the two dimensions of the total number of monsters and the blood volume are considered in the design of the fitness function in the generation method, and the three dimensions are very close because the prior correlation degree of the total reward of monsters and the blood volume of monsters is high. The relative difference between the odd density and the odd density is large, so the odd interval needs to be adjusted.
Step S210, adjust the strange configuration.
In one embodiment of the present invention, the allocation of the monsters mainly includes the number of monsters, the amount of blood of monsters, the number of bonus of monsters, and the density of monsters.
For the generation checkpoints illustrated in fig. 7-9, it is the monster density that mainly needs to be adjusted. The density of the odd-shaped objects can be adjusted by changing the interval between the genes in the odd-shaped objects to adjust the odd-shaped time of a wave under the condition of a certain number of odd-shaped objects.
During adjustment, when a gene sequence generated by a genetic algorithm (in a form before conversion into a checkpoint configuration) is converted into checkpoint configuration information, interval parameters (time interval between each gene and a monster segment) can be gradually changed to generate candidate checkpoint configurations, a monster density evaluation in an evaluation method is called to evaluate the candidate checkpoint configurations, an interval parameter with a score of an evaluation result closest to a comparison checkpoint (corresponding to an original checkpoint) is selected, and the checkpoint configuration is generated by the interval parameter to serve as a finally generated checkpoint configuration.
FIG. 10 is a comparison of the estimated checkpoint monster density after adjustment with the original checkpoint. As can be seen from fig. 10, compared to before the adjustment of the density of the monsters (see (d) in fig. 7), the degree of similarity between the newly generated level in terms of the density of the monsters after the adjustment and the original level is greatly improved, that is, after the configuration parameters of the level are adjusted by the evaluation score, a more ideal level is generated.
FIG. 11 is a flowchart illustrating a method for generating a monster configuration in an embodiment of the invention. As shown in fig. 11, the process includes the following steps:
step S1101, a gene pool is constructed.
This step can refer to step S110 described above, and is not described herein again.
Step S1102, 1000 individuals are randomly generated as the primary population.
This step can be implemented with reference to the previously described steps S120-S130, which are not described in detail herein.
Step S1103, for the current population, the fitness value fitness of each individual gene checkpoint is calculated, and the smallest fitness value is selected.
In step S1104, it is determined whether the minimum fitness value is smaller than a predetermined threshold? If so, the corresponding individual may be output as an available individual, i.e., the genotype result of the corresponding individual is output (step S1109). In the embodiment of the present invention, the predetermined threshold (before normalization) may be, for example, any extremely small positive number, and may range from 10e-3 to 10e-8, such as 10e-6, but the present invention is not limited thereto. If not, step S1105 may be entered to continuously determine whether the minimum fitness value is unchanged for n consecutive generations (the value of n indicates the severity of the convergence condition, and the range may be any positive integer, such as 10), that is, the evolution has reached convergence, and if so, the corresponding individual may be output as an available individual, thereby performing step S1109. If not, it indicates that there are no available genetic checkpoint individuals in the current checkpoint individuals, and then the process proceeds to step S1106.
In step S1106, a predetermined number (for example, 20%, the ratio is only an example, and the present invention is not limited thereto) of the genetic checkpoint individuals with the smallest fitness value are selected as parents from the current population in order of the smallest fitness value.
In step S1107, the parent is crossed to generate a predetermined number (e.g. 1000) of children.
In step S1108, a mutation operation is performed on a predetermined number or percentage (e.g., 20% or 30%) of new individuals.
In this step, the total number is kept constant compared to the original population, and a predetermined proportion of newly produced individuals and a remaining proportion of parent individuals may be combined into a new generation of population.
For example, 800 newly generated individuals (including the portion that has mutated) +200 parents are grouped into a new generation of population. And simultaneously, the process goes to step S1103 to recalculate the fitness value of each individual in the new population.
Step S1109, after the usable gene checkpoint individual is found through judging the fitness value, the genotype result of the individual is output.
Step S1110, converting the output genotype result of the available individual genetic checkpoint into a checkpoint configuration asking price format, which is the same as step S190 described above and will not be described herein again.
Step S1111, using the configuration parameters to evaluate the level from multiple dimensions and recording the evaluation result (e.g. evaluation value), as described in step S200.
In step S1112, a strange configuration is adjusted based on the evaluation result.
As in step S210 described previously. In this step, the level of the gap parameter can be adjusted within the range of [150 frames, 1801 frames) and using 50 frames as the step size, and the switching checkpoint configuration is operated circularly.
And S1113, outputting the optimal individual gene checkpoint based on the adjustment result.
In this step, each level configuration after the configuration parameters are adjusted is evaluated, and the level configuration with the best evaluation result is selected as the final level result.
In the embodiment of the present invention, if the steps S1103 to S1105 are iterated to 1000 generations of population and no gene level individual output is available, the process is directly exited, and the evolution process is ended.
The method for generating the configuration of the monster comprises the steps of using a small fixed monster pattern designed in advance by human beings as a gene segment (genotype), jointly restricting a fitness function of the configuration of the level from multiple dimensions, combining the genes designed by the human beings by using a genetic algorithm and generating a new level, evaluating the generated level by multiple dimensions, checking the performance of an individual generated level, and adjusting the generated level by evaluating a score, so as to generate a more appropriate level.
The above method of the embodiment of the present invention can be implemented on a computer by executing a computer program. Thus, the present invention provides a game monster configuration generation apparatus, as shown in FIG. 12, that includes a processor 910, which may be, for example, a CPU, microprocessor, or the like, and a memory 920. Memory 920 is configured to store computer instructions and processor 910 is configured to execute computer instructions stored in the memory, which when executed by the processor, is configured to perform a game monster configuration generation method as described above. Optionally, the apparatus may further include a transmission interface (wired interface or wireless network interface) 930 and a display 940. The transmission interface 930 is used to communicate with an external device to transmit data. Display 940 may be used to display assessment results, a strange pattern display of checkpoints, and the like. The configuration shown in fig. 12 is merely an example, and may include more or fewer components.
The present disclosure also relates to a storage medium, which may be a tangible storage medium such as an optical disk, a usb disk, a floppy disk, a hard disk, etc., on which computer program code may be stored, which when executed may implement various embodiments of the game path generation method of the present invention.
Those of ordinary skill in the art will appreciate that the various illustrative elements and method steps described in connection with the embodiments disclosed herein may be implemented as hardware, software, or combinations of both. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the implementation. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention.
The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied in software executed by hardware (a logic device such as a computer). The software, when executed, may cause the hardware (computer or other logic device) to implement the methods or its constituent steps described above, or cause the hardware (computer or other logic device) to function as apparatus components of the invention described above.
The software may be disposed in Random Access Memory (RAM), memory, read Only Memory (ROM), electrically programmable ROM, electrically erasable programmable ROM, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art.
Features that are described and/or illustrated with respect to one embodiment may be used in the same way or in a similar way in one or more other embodiments and/or in combination with or instead of the features of the other embodiments in the present invention.
The embodiments described above are exemplary rather than limiting and those skilled in the art will appreciate that various modifications and alterations can be made in the spirit of the invention and that such modifications and alterations are also within the scope of the invention.
Claims (16)
1. A method of generating a monster configuration for a game, the method comprising the steps of:
a gene pool construction step: constructing at least one gene pool comprising a plurality of monster configuration gene segments, wherein the gene segments comprise gene numbers and monster gene information, and the monster gene information comprises monster matrix type information;
checkpoint genotype representation generation step: generating a plurality of checkpoint genotype representations based on the gene segments in the gene pool, each checkpoint genotype representation including monster wave information, path information corresponding to each wave, and gene representations of monsters on each path corresponding to each wave, wherein the gene representations of monsters on each path corresponding to each wave include gene segment placeholders of a particular length;
generating a primary population: generating a preliminary population comprising a predetermined number of genetic checkpoint individuals based on the plurality of checkpoint genotype representations;
and a fitness calculation step: calculating the fitness of each gene checkpoint individual in the currently generated population;
an individual selection step: determining whether available gene level individuals exist or not based on the calculated fitness of each gene level individual, and screening out a preset proportion or number of gene level individuals from the current population as parent gene level individuals based on the calculated fitness of each gene level individual under the condition that the available gene level individuals do not exist;
an evolution step: generating a population of a new generation of genetic checkpoint individuals by utilizing a genetic algorithm based on the parent genetic checkpoint individuals;
and repeating the fitness calculating step, the individual selecting step and the evolving step until the existence of the available genetic checkpoint individuals is determined based on the calculated fitness of each genetic checkpoint individual, outputting the available genetic checkpoint individuals, and generating a monster configuration based on the output genetic checkpoint individuals.
2. The method of claim 1, wherein generating a monster configuration for the individual based on the output-based genetic checkpoint comprises:
generating a strange configuration in a checkpoint profile based on the outputted checkpoint genotype representation for the genetic checkpoint individual.
3. The method of claim 2, wherein the strange configuration in the level profile further comprises at least one of the following configuration parameters: the number of the monsters, the blood volume of the monsters, the number of the monsters and the density of the monsters;
the method further comprises the following steps: and evaluating strange configurations in the level configuration file by using the configuration parameters.
4. The method of claim 3, further comprising:
at least one configuration parameter in the strange configuration is adjusted, and the optimal strange configuration is selected based on the adjusted evaluation result.
5. The method of claim 1, wherein prior to the step of constructing a gene pool, the method further comprises:
a plurality of monster configuration gene segments are generated based on configuration data of the original checkpoint.
6. The method of claim 5, wherein the step of generating a plurality of monster configuration gene segments based on the configuration data of the original checkpoint comprises:
and splitting the configuration data of each wave of monsters in the original checkpoint according to the paths, and generating a plurality of monster configuration gene segments based on the occurrence time intervals and distribution among the monsters on each path.
7. The method according to any one of claims 1-6, wherein:
the informational elements in the monster configuration gene segments, the informational elements in the checkpoint genotype representation, and/or the gene segment placeholder sequences of a particular length are configured in a list format.
8. The method of any one of claims 1 to 6, wherein the at least one gene pool is constructed as a plurality of segmented gene pools corresponding to different checkpoint levels or different monster bands, respectively.
9. The method of any one of claims 1 to 6, wherein the gene segment placeholder sequences in the checkpoint genotype representation are generated by random placeholder for gene segments in the corresponding gene pool.
10. The method of claim 9, wherein the step of generating a preliminary population of a predetermined number of genetic checkpoint individuals based on the plurality of checkpoint genotype representations comprises:
expressing the gene level genotypes of a predetermined number as gene level individuals of a predetermined number, and generating a gene level individual primary population; or
Generating a preliminary population of a predetermined number of genetic checkpoint individuals using a plurality of checkpoint genotype representations and genetic codes configured to indicate whether there is a monster on each primary path of each wave in the current checkpoint.
11. The method of any one of claims 1-6, wherein calculating the fitness of each individual genetic checkpoint in the currently generated population comprises: calculating the fitness of each gene checkpoint individual in the currently generated population by using a fitness function;
the fitness function is a fitness function determined based on at least one of the following parameters: monster number, monster species, monster blood volume, and monster density.
12. The method of claim 11, wherein the fitness function formula is three functions f N 、f T，T′ And f H In which f is N F is a function for measuring the similarity of the current genetic checkpoint individual and the reference checkpoint individual based on the number of monsters T，T′ F is a function for representing the similarity of the current genetic checkpoint individual and the reference checkpoint individual measured based on the category of monsters H Is a function representing the measure of similarity of the current genetic checkpoint individual to the reference checkpoint individual based on the monster blood volume.
13. The method of claim 12, wherein:
f N ＝d 1 (N c ，N r )+d 2 (N c ，N r )+|∑N c +∑N r |；
f T，T′ ＝θ 1 d 1 (T c ，T r )+θ 2 |T c ′-T r ′|；
f H ＝θ 3 d 1 (H c ，H r )+θ 4 d 2 (H c ，H r )；
where Nc and Nr represent the number of monsters appearing in each wave for the current gene level and the reference level, respectively, tc and Tr represent the number of types of monsters appearing in each wave for the current gene level and the reference level, respectively, hc and Hr represent the sum of blood volumes of monsters appearing in each wave for the current gene level and the reference level, respectively, tc 'and Tr' represent the number of types of monsters appearing in the entire levels of the current gene level and the reference level, respectively, and function d 1 Calculating a function for the Manhattan distance, function d 2 For cosine similarity calculation function, theta 1 ，θ 2 ，θ 3 ，θ 4 Respectively, are weight coefficients.
14. The method of claim 1, wherein the evolving step comprises:
and (3) carrying out cross operation and/or mutation after disorder on the parent gene checkpoint individual population to generate a new gene checkpoint individual, thereby generating a new generation gene checkpoint individual population comprising the new gene checkpoint individual and part or all of the parent gene checkpoint individual.
15. A monster configuration generating device for a game, comprising a processor and a memory, the memory for storing computer instructions, the processor for executing the computer instructions stored in the memory, the monster configuration generating device implementing the steps of the method of any one of claims 1-14 when the processor executes the computer instructions stored on the memory.
16. A computer-readable storage medium, in which a computer program is stored which, when being executed by a processor, carries out the steps of the method according to any one of claims 1 to 14.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811534241.9A CN109615074B (en) | 2018-12-14 | 2018-12-14 | Method and device for generating monster configuration of game |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811534241.9A CN109615074B (en) | 2018-12-14 | 2018-12-14 | Method and device for generating monster configuration of game |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN109615074A CN109615074A (en) | 2019-04-12 |
| CN109615074B true CN109615074B (en) | 2023-02-17 |
Family
ID=66009182
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201811534241.9A Active CN109615074B (en) | 2018-12-14 | 2018-12-14 | Method and device for generating monster configuration of game |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109615074B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110339563B (en) * | 2019-07-09 | 2023-09-26 | 腾讯科技（深圳）有限公司 | Virtual object generation method and device, storage medium and electronic device |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1450493A (en) * | 2003-04-25 | 2003-10-22 | 北京工业大学 | Nerve network system for realizing genetic algorithm |
| CN101047937A (en) * | 2006-03-27 | 2007-10-03 | 浙江移动通信有限责任公司 | Mobile communication frequency planning method based on genetic algorithm |
| CN104112237A (en) * | 2014-06-30 | 2014-10-22 | 国家电网公司 | WAMS-based genetic algorithm-improved power grid reactive capacity optimization configuration method |
| CN104811491A (en) * | 2015-04-17 | 2015-07-29 | 华南理工大学 | Cloud computing resource scheduling method based on genetic algorithm |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20140149624A1 (en) * | 2012-11-29 | 2014-05-29 | Lsi Corporation | Method for Determining a Serial Attached Small Computer System Interface Topology |
-
2018
- 2018-12-14 CN CN201811534241.9A patent/CN109615074B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1450493A (en) * | 2003-04-25 | 2003-10-22 | 北京工业大学 | Nerve network system for realizing genetic algorithm |
| CN101047937A (en) * | 2006-03-27 | 2007-10-03 | 浙江移动通信有限责任公司 | Mobile communication frequency planning method based on genetic algorithm |
| CN104112237A (en) * | 2014-06-30 | 2014-10-22 | 国家电网公司 | WAMS-based genetic algorithm-improved power grid reactive capacity optimization configuration method |
| CN104811491A (en) * | 2015-04-17 | 2015-07-29 | 华南理工大学 | Cloud computing resource scheduling method based on genetic algorithm |
Also Published As
| Publication number | Publication date |
|---|---|
| CN109615074A (en) | 2019-04-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Li et al. | Emergent world representations: Exploring a sequence model trained on a synthetic task | |
| Clark et al. | Training deep convolutional neural networks to play go | |
| Adams et al. | Procedural maze level generation with evolutionary cellular automata | |
| Maher et al. | Formalising design exploration as co-evolution: a combined gene approach | |
| Dahlskog et al. | A multi-level level generator | |
| CN118873914B (en) | A method and system for generating a fitness exercise program based on optimization algorithm | |
| CN109087375A (en) | Image cavity fill method based on deep learning | |
| Liu et al. | Automatic generation of tower defense levels using PCG | |
| CN110458295B (en) | Chess and card level generation method, training method and device based on artificial intelligence | |
| CN109615074B (en) | Method and device for generating monster configuration of game | |
| Shu et al. | A novel cnet-assisted evolutionary level repairer and its applications to Super Mario Bros | |
| de Freitas et al. | Evolving controllers for mario AI using grammar-based genetic programming | |
| Li et al. | Speedup training artificial intelligence for mahjong via reward variance reduction | |
| Zhou et al. | Discovering of game AIs’ characters using a neural network based AI imitator for AI clustering | |
| Zhang et al. | The cooperative evolution in the spatial prisoner's dilemma game with the local loyalty of two-strategy | |
| CN114219605A (en) | A wind control method, device and storage medium | |
| Galván-López et al. | Defining locality in genetic programming to predict performance | |
| Bhatt et al. | In search of no-loss strategies for the game of tic-tac-toe using a customized genetic algorithm | |
| CN114841311A (en) | Deep reinforcement learning landlord game method based on split action space | |
| Zhao et al. | Building a 3-player Mahjong AI using deep reinforcement learning | |
| Q. Tomas et al. | Developing an Adaptive AI Agent using Supervised and Reinforcement Learning with Monte Carlo Tree Search in FightingICE | |
| Cerezo et al. | Solving Atari Games using fractals and entropy | |
| Dukkancı | Level generation using genetic algorithms and difficulty testing using reinforcement learning in match-3 game | |
| Siper et al. | Controllable path of destruction | |
| Turney | Conditions for open-ended evolution in immigration games |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| TA01 | Transfer of patent application right |
Effective date of registration: 20200201 Address after: 100041, room 2, building 3, building 30, Xing Xing street, Shijingshan District, Beijing, Applicant after: BEIJING BYTEDANCE NETWORK TECHNOLOGY Co.,Ltd. Address before: 100083 the first floor of the western small building, No. 18, No. 18, Xue Qing Lu Jia, Beijing Applicant before: BEIJING SHENJI TECHNOLOGY CO.,LTD. |
|
| TA01 | Transfer of patent application right | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |