Chinaunix

标题: 游戏开发中常用的2d和3d图形算法有哪些 [打印本页]
作者: skychongrichie    时间: 2013-12-30 01:03
标题: 游戏开发中常用的2d和3d图形算法有哪些
最近，准备换工作，浏览招聘信息时，发现很多游戏公司招聘要求中都有熟悉常用的2d和3的图形算法，可是这些图形算法有哪些呢？望各位不吝赐教哈，先在这里提前谢过了
作者: skychongrichie    时间: 2013-12-30 23:54
自己先顶下
作者: skychongrichie    时间: 2013-12-30 23:56
各种路径搜索，DFS，BFS，各种树？
作者: BlueGuy_    时间: 2014-01-03 08:50
提示: 作者被禁止或删除 内容自动屏蔽
作者: skychongrichie    时间: 2014-01-04 11:53
本帖最后由 skychongrichie 于 2014-01-04 11:54 编辑

回复 4# BlueGuy_ DFS大学的数据结构课上应该有吧，应该算是很基础的。谢回复


   
作者: BlueGuy_    时间: 2014-01-04 12:43
提示: 作者被禁止或删除 内容自动屏蔽
作者: BlueGuy_    时间: 2014-01-04 12:51
提示: 作者被禁止或删除 内容自动屏蔽
作者: skychongrichie    时间: 2014-01-06 22:20
回复 7# BlueGuy_ 你高中生啊？这么牛？当年我高中的时候连c++是啥都不知道，见笑了哈。言归正传，我还没用DFS求过组合数呢，实际应用中用的最多是遍历某种树形结构，就一个典型的深度优先搜索来说，的确很easy啊


   
作者: BlueGuy_    时间: 2014-01-06 22:28
提示: 作者被禁止或删除 内容自动屏蔽
作者: BlueGuy_    时间: 2014-01-06 22:30
提示: 作者被禁止或删除 内容自动屏蔽
作者: BlueGuy_    时间: 2014-01-06 22:58
提示: 作者被禁止或删除 内容自动屏蔽
作者: Susake_    时间: 2014-01-07 07:07
本帖最后由 Susake_ 于 2014-01-08 13:56 编辑
skychongrichie 发表于 2014-01-06 22:20
回复 7# BlueGuy_ 你高中生啊？这么牛？当年我高中的时候连c++是啥都不知道，见笑了哈。言归正传，我还没用 ...

STL中就有一个next_permutation

  2. #include <iostream>   
  3. #include <algorithm>  
  4. using namespace std;

  6. int main(int argc, char *argv[])
  7. {
  8.         int array_n[] = {1, 2, 3};

  10.         sort(array_n, array_n + 3);

  12.         do
  13.         {
  14.                 cout << array_n[0] << " " << array_n[1] << " " << array_n[2] << endl;
  15.         }
  16.         while(next_permutation(array_n, array_n + 3));

  18.         return 0;
  19. }
复制代码
作者: captivated    时间: 2014-01-07 19:31
回复 12# Susake_


    next_permutation 不是 dfs 的, 是通过找到 下降位置, 交换, 逆序 做的. 再说, qsort 什么的也有现成的, 不过这种问题, 自己还是撸过一遍比较好.

作者: captivated    时间: 2014-01-07 19:40
回复 6# BlueGuy_

    大侠, 麻烦给看看是不是这个啊.

    这个好像是排列的, 大侠给个组合的嘛.
  1. #include <stdio.h>

  3. #define LEN        10

  5. // index: 记录下标
  6. // mark:  记录是否选取过
  7. // a: 要排列的数组
  8. // n: 数组中元素个数
  9. // m: 要从 n 个元素中选多少个
  10. // depth: 递归深度
  11. void perm_dfs(int index[], int mark[], int a[], int n, int m, int depth)
  12. {
  13.         int i;

  15.         if (depth == m)
  16.         {
  17.                 for (i = 0; i < m; i++)       
  18.                         printf("%d ", a[index[i]]);       
  19.                 putchar('\n');
  20.         }
  21.         else
  22.         {
  23.                 for (i = 0; i < n; i++)       
  24.                 {
  25.                         if (0 == mark[i])
  26.                         {
  27.                                 index[depth] = i;       
  28.                                 mark[i] = 1;

  30.                                 perm_dfs(index, mark, a, n, m, depth + 1);

  32.                                 mark[i] = 0;
  33.                         }
  34.                 }
  35.         }
  36. }

  38. int main(void)
  39. {
  40.         int index[LEN], mark[LEN] = { };
  41.         int a[LEN] = { 4, 6, 8, 9 };
  42.         perm_dfs(index, mark, a, 4, 4, 0);

  44.         return 0;
  45. }
复制代码
作者: BlueGuy_    时间: 2014-01-07 19:41
提示: 作者被禁止或删除 内容自动屏蔽
作者: BlueGuy_    时间: 2014-01-07 19:42
提示: 作者被禁止或删除 内容自动屏蔽
作者: captivated    时间: 2014-01-07 19:44
回复 16# BlueGuy_


    哦, 是这个吗, 这个原创是你不
  1. #include <stdio.h>

  3. #define MAX 100

  5. // a: 存放候选数字
  6. // n: 总项数
  7. // m: 取出项数
  8. // b: 存放选出结果
  9. // M = m
  10. void combine(int a[], int n, int m, int b[], int M)
  11. {
  12.         int i, j;

  14.         for (i = n; i >= m; i--)
  15.         {
  16.                 b[m - 1] = i - 1;       
  17.                 if (m > 1)
  18.                         combine(a, i - 1, m - 1, b, M);
  19.                 else
  20.                 {
  21.                         for (j = M - 1; j >= 0; j--)       
  22.                                 printf("%d ", a[b[j]]);
  23.                         putchar('\n');
  24.                 }
  25.         }
  26. }

  28. int main(void)
  29. {
  30.         int i;
  31.         int a[MAX], b[MAX];

  33.         for (i = 0; i < 100; i++)
  34.                 a[i - 1] = i;

  36.         combine(a, 5, 4, b, 4);

  38.         return 0;
  39. }
复制代码
作者: captivated    时间: 2014-01-07 19:45
回复 16# BlueGuy_


    我会写象棋, 大侠收了我吧.
作者: BlueGuy_    时间: 2014-01-07 19:48
提示: 作者被禁止或删除 内容自动屏蔽
作者: BlueGuy_    时间: 2014-01-07 19:50
提示: 作者被禁止或删除 内容自动屏蔽
作者: captivated    时间: 2014-01-07 19:51
回复 20# BlueGuy_


    切. 不就一个深搜加估值么. 我抄的.
作者: BlueGuy_    时间: 2014-01-07 19:55
提示: 作者被禁止或删除 内容自动屏蔽
作者: BlueGuy_    时间: 2014-01-07 19:58
提示: 作者被禁止或删除 内容自动屏蔽
作者: captivated    时间: 2014-01-07 19:59
回复 22# BlueGuy_


    算了. QQ号暂时不给, 怕跨省. 开玩笑的. 我比较少发言, 不爱玩那个.
    如果我哪天想加入你的群了, 大侠你就收了我的意思.

作者: BlueGuy_    时间: 2014-01-07 20:00
提示: 作者被禁止或删除 内容自动屏蔽
作者: captivated    时间: 2014-01-07 20:01
回复 23# BlueGuy_


    最近在写个自娱自乐的解释器, 不知道能算作品不.

    我就一臭教书的, 不玩产品的. 没事我还要玩儿一下 ARM 板子什么的, 所以没时间做产品啊.
作者: BlueGuy_    时间: 2014-01-07 20:03
提示: 作者被禁止或删除 内容自动屏蔽
作者: Susake_    时间: 2014-01-07 22:47
本帖最后由 Susake_ 于 2014-01-08 07:35 编辑

回复 14# captivated
empty


   
作者: Susake_    时间: 2014-01-07 23:16
本帖最后由 Susake_ 于 2014-01-08 13:42 编辑
BlueGuy_ 发表于 2014-01-07 19:42
排列比较简单，大家都会写，网上都一堆，因为他们都没动过脑子
组合是我原创出来的算法，

嗯嗯...没深究qsort这些内部如何实现的,只是暂时拿来用用...
好吧,我把排列当成组合了....
作者: Susake_    时间: 2014-01-07 23:25
回复 13# captivated
http://bbs.bccn.net/viewthread.p ... p;page=1#pid2288916
第四个就是我说的递归回溯的排列..!
作者: captivated    时间: 2014-01-08 12:01
回复 30# Susake_


    你那个全排列是无序的.
作者: skychongrichie    时间: 2014-01-10 10:11
回复 10# BlueGuy_ 告诉你，我现在已经做了1年多手游，可惜不是棋牌的，大学的数据结构DFS主要用来做图或树的遍历，所以到现在我都没机会接触到用DFS求组合数的机会，也从来没有研究过，你说我不会DFS，我也只能呵呵。还有后面螺丝钉什么的，希望你以后话不要说的那么难听，搞得你已经成比尔盖茨第二似的。


   
作者: BlueGuy_    时间: 2014-01-10 14:41
提示: 作者被禁止或删除 内容自动屏蔽



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2